KMP算法中next数组求法.docx
版权申诉
5星 · 超过95%的资源 179 浏览量
2022-05-06
16:00:59
上传
评论
收藏 17KB DOCX 举报 
KMP 算法中 next 数组求法
next[] 数组的定义为(相对 c++):
next[0]= -1;
next[i] ( i>0 ) 为： 对于模式串 S[], 我们用 S[i, j] 表示从 S[] 中 i 到 j 这一段子串。 找一
个 k(0< k< i ) 使得，
S[0, k-1]与 S[i- k, i-1]完全匹配，并且 k 的值最大， 那么 next[i]= k; 如果不存在完全匹
配的，next[i]= 0;
0 1 2 3 4 5 6 7
如对于串 a b a a b c a c , next[0]= -1, 显然 next[1]= 0;
i== 2 时， 满足 0< k< 2 的 k 只有 1, 而 S[0, 0] 与 S[1,1] 不完全匹配，所以 next[2]=
0;
i== 3 时， 满足 0< k< 3 的 k 有 1, 2, S[0,1] 'ab' 与 S[1,2] 'ba' 不完全匹配，S[0,0]
'a' 与 S[2,2] ’a' 完全匹配， 故 next[3]= 1;
i==4 时， S[0,2] ’aba' != S[1,3] 'baa' S[0,1] 'ab'!= S[2,3] 'aa' S[0,0]==
S[3,3]，故 next[4]= 1;
同理： next[5]= 2, next[6]= 0, next[7]= 1;
可以用递推的方法求得 next[] 数组
假设 next[i]= k, 则有 S[0, k-1]== S[i-k, i-1], 如何求 next[i+1]?
1). 如果 S[k]== S[i+1], 则有 S[0,k]== S[i-k, i], 可以肯定，不可能存在 x> k, 使得 S[0,
x]== S[i-x, i] 故 next[i+1]= next[i]+ 1= k+ 1;
2). 如果 S[k]!= S[i+1], 可看成是一个模式匹配问题，相当于 S[len(S)-K, len(S)]为主
串， S[0, len(S)]为模式串的模式匹配，这时应将模式串向右滑动 next[k] 个字符， 再比较
S[ next[k] ]与 S[i+1]， 如果相等， 则 next[i+1]= next[ next[k] ]+ 1, 如此继续。
代码：
void get_next(){
next[0]= -1;
int i= 0, j= -1;
while( str[i] ){
if( j== -1 || str[i]== str[j] ){
i++; j++; next[i]= j;
}
else j= next[j];
}
}
- 1
- 2
前往页