SIVERSITY ScIE\CE TECH\OLoGY CHINA COMPUTE-PREFX-FUNCTION(P) I m= Plength 2 let [I.. ml be a new amay 3r1]=0 k=0 5 for q= 2 to m while>0 and Pk+l≠Pll 67890 k= xkI if Pk+l]== Plal k=k+1 ql=k 11 retum m 021/2 21 &T
2021/2/4 Department of Computer Science & Technology 21
NIVERSI OFScIenCE TECHNOLoGY KMP算法实例 CHINA Search Text n nee ne l de ne e d l e n l d Next(P Search Pattern e n e 011123 2.m← Length(P); 3.Fori←1 to m do i=1,j=0,Next[1]=0 4.Next←j; i=2,j=1,Next2]=1 While j>0andP[≠ PLI do 1=3,j=1,Next3]=1 j← Nextli i=4. Next 4]=1 7. +1 Next5=2 6,j=2,Next[6]=3 P2/4 22
2021/2/4 22 n n e e n e Search Text l d e n e e n e e d l e n l d n e e n e e Search Pattern i = 1, j = 0, Next[1] = 0 i = 2, j = 1, Next[2] = 1 i = 3, j = 1, Next[3] = 1 i = 4, j = 1, Next[4] = 1 i = 5, j = 1, Next[5] = 2 i = 6, j = 2, Next[6] = 3 0 1 1 1 2 3 Next(P) 1. j ← 0; 2. m ← Length(P) ; 3. For i ← 1 to m do 4. Next[i] ← j ; 5. While j > 0 and P[i]≠P[j] do 6. j ← Next[j] ; 7. j ← j + 1; KMP算法实例
ence TEChNOLoGY KMP算法实例 CHINA Search Text nnee l deneeneedlenld Search Pattern nee ne e 从文本串T的最左端开始匹配 KMP(T, P) Search Pattern 2.Fori←1 to n do nee ne e while>0andT≠P[i]do 011123 4 j←Next]; ifj= m then∥找到一个成功匹配 return(i-m+1) 7 」←J+ 8. return(none) P2/4
2021/2/4 23 n n e e n e Search Text l d e n e e n e e d l e n l d n e e n e e Search Pattern 0 1 1 1 2 3 KMP(T, P) 1. j ← 1; 2. For i ← 1 to n do 3. while j > 0 and T[i] ≠ P[j] do 4. j ← Next[j] ; 5. if j = m then // 找到一个成功匹配 6. return (i-m+1) ; 7. j ← j +1 ; 8. return （none） n e e n e e Search Pattern 从文本串T的最左端开始匹配 KMP算法实例
ence TEChNOLoGY KMP算法实例 CHINA Search Text nnee l deneeneedlenld Search Pattern 1,i=1,P[]=T1l,则: nee ne e j+1,i=i+1,比较Pi]和Ti KMP(T, P) Search Pattern 2.Fori←1 to n do nee ne e while>0andT≠P[i]do 011123 4 j←Next ifj= m then∥找到一个成功匹配 return(i-m+1) 7 」←J+ 8. return(none) P2/4
2021/2/4 24 n n e e n e Search Text l d e n e e n e e d l e n l d n e e n e e Search Pattern 0 1 1 1 2 3 KMP(T, P) 1. j ← 1; 2. For i ← 1 to n do 3. while j > 0 and T[i] ≠ P[j] do 4. j ← Next[j] ; 5. if j = m then // 找到一个成功匹配 6. return (i-m+1) ; 7. j ← j +1 ; 8. return （none） n e e n e e Search Pattern j = 1, i = 1, P[1] = T[1], 则： j = j + 1, i = i + 1, 比较 P[j]和T[i] ? KMP算法实例
ence TEChNOLoGY KMP算法实例 CHINA Search Text nnee l deneeneedlenld SE Search Pattern 2,i=2,P[2]≠T[2],则: nBe日Bee Next[2],比较P订和Ti KMP(T, P) Search Pattern 2.Fori←1 to n do nee ne e while>0andT≠P[i]do 011123 4 j←Next ifj= m then∥找到一个成功匹配 return(i-m+1) 7 +1 8. return(none) 22/4 225
2021/2/4 25 n n e e n e Search Text l d e n e e n e e d l e n l d 0 1 1 1 2 3 KMP(T, P) 1. j ← 1; 2. For i ← 1 to n do 3. while j > 0 and T[i] ≠ P[j] do 4. j ← Next[j] ; 5. if j = m then // 找到一个成功匹配 6. return (i-m+1) ; 7. j ← j +1 ; 8. return （none） n e e n e e Search Pattern n e e n e e Search Pattern j = 2, i = 2, P[2] ≠ T[2], 则： j = Next[2], 比较 P[j]和 T[i] n e e n e e Search Pattern KMP算法实例