KMP的Next数组.ppt

文档介绍：串的模式匹配算法
定义在串中寻找子串(第一个字符)在串中的位置
词汇在模式匹配中,子串称为模式,串称为目标。
示例目标 S : “Beijing”
模式 P : “jin”
匹配结果= 4
主串如下:
a c a b a a b a a b c a c a a b c
a b a a b c
(a b)a a b c
此时不匹配,i和j应该如何变化?
Next[6]= 3 = 2+1
模式串 a b a a b c a c
i=8
j=6
j=3
为什么这几位不用比较,可以直接从第3位比?
①
②
③
因为①=②
②=③
所以①=③
可直接从第3位比
a b a a b c
i=4
j=1
i回到4号位置继续与模式的第一个字符比?
不需要
KMP算法
int Index_KMP(SString S, SString T, int pos)
{ // 利用模式串T的next函数求T在主串S中第pos个
// 字符之后第一次出现的位置;否则返回0。
i = pos; j = 1;
while(i<=S[0] && j <= T[0]){
if(j = = 0 || S[i] = = T[j]){ ++i; ++j;}
// 继续比较后续字符
else j = next[j]; // 模式串向后移
}
if(j > T[0]) return i-T[0]; // 匹配成功
else return 0; // 匹配不成功
} // Index_KMP
KMP算法的匹配过程示例
任选一主串举例如下:
第一趟 a c a b a a b a a b c a c a a b c (i=2)
a b (j=2,next[2]=1)
第二趟 a c a b a a b a a b c a c a a b c (i=2)
a (j=1,next[1]=0)
第三趟 a c a b a a b a a b c a c a a b c (i=8)
a b a a b c (j=6,next[6]=3)
第四趟 a c a b a a b a a b c a c a a b c (i=14)
(a b)a a b c a c (j=9,成功)
j 1 2 3 4 5 6 7 8
模式串 a b a a b c a c
next[j] 0 1 1 2 2 3 1 2
if(j > T[0]) return i-T[0]; // 匹配成功
假设当模式中第j个字符与主串中相应字符“失配”时,可以拿第k个字符来继续比较,则令next[j]=k
next函数定义:
0 当j=1时
next[j]= Max{k| 1<k<j 且’p1…pk-1’=‘pj-k+1…pj-1’}