Question

那个，KMP算法里面 求模式串的next[]数组的方法看不懂； 有大神能详细解释一下不，看不懂哇？

Answer 1

对于next[]数组
也就是子串的某个位置与自身的公共前缀的最后匹配位置。
这样讲可能有点抽象，说白了就是子串以该位置为最末位，自己和自己匹配的最长公共前缀。

而在进行next[]数组的第i个位置的求值时，该位置以前的所有next[]值已经求出，因此我们可以借助之前求出的next[]值来更新此刻next[i]的值。

所以时间复杂度为O(2*m)

拿ababac来说：
第一步：
ababac
_ababac
i，j在一开始就失配，即next[2]=0。

第二步：
ababac
__ababac
i，j在第3位匹配，next[3]=1
同理：next[4]=2，next[5]=3，next[6]=4

在i=6，j=4时失配。

因此，将j=next[j]+1，i++，也就是匹配串后移。
即：
ababac
______ababac
此时，两串失配，next[7]=0

求next[]数组代码：
int next[100];
char str2[100];
void get_next()
{
int len2=strlen(str2);
int i=1,j=0;
while(i<len2)
{
if(j==0 || str2[i]==str2[j])
{
i++;j++;
next[i]=j;
}
else
j=next[j];
}
}