ence TEChNOLoGY KMP算法实例 CHINA Search Text nnee l deneeneedlenld Search Pattern 1,i=2,P[]=T2],则 nee ne e j+1,i=计+1;,比较P[2和T3] 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 26 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 j = 1, i = 2, P[1] = T[2], 则： j = j + 1, i = i+1; 比较 P[2]和 T[3] n e e n e e Search Pattern ? KMP算法实例
ence TEChNOLoGY KMP算法实例 CHINA Search Text nnee l deneeneedlenld Search Pattern 2,i=3,P2]=T[3],则: nee ne e j+1,i=计+1;,比较P[3]和T4 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) P2/4 227
2021/2/4 27 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 = 3, P[2] = T[3], 则： j = j + 1, i = i+1; 比较 P[3]和 T[4] ? KMP算法实例
ence TEChNOLoGY KMP算法实例 CHINA Search Text nnee l deneeneedlenld Search Pattern 3,i=4,P[B3]=T4],则: nee ne e +1,i=计+1;比较P[4和T5 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) P2/4 228
2021/2/4 28 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 = 3, i = 4, P[3] = T[4], 则： j = j + 1, i = i+1; 比较 P[4]和 T[5] ? KMP算法实例
ence TEChNOLoGY KMP算法实例 CHINA Search Text nnee l deneeneedlenld Search Pattern 4,i=5,P4]=T[5],则: nee ne e j+1,i=计+1;,比较P[5和T6] 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 29 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 = 4, i = 5, P[4] = T[5], 则： j = j + 1, i = i+1; 比较 P[5]和 T[6] ? KMP算法实例
ence TEChNOLoGY KMP算法实例 CHINA Search Text nnee l deneeneedlenld Search Pattern 5,i=6,P[5]=T6],则: nee ne e +1,i=计+1;比较P[6和T7] 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) P2/4 230
2021/2/4 30 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 = 5, i = 6, P[5] = T[6], 则： j = j + 1, i = i+1; 比较 P[6]和 T[7] ? KMP算法实例