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];
    }
}