Question

C++ ACM KMP算法最，那个函数实在是看不懂~网上的大牛也只贴代码没解释，所以来求神牛帮忙解释一下~！

貌似所主要就是这个next数组，我看到这2种版本~应该是一样的把~只是我2种都看不懂呢，求详细解释啊~！

void getNext()
{
next1[1] = 0;
int i, j = 0;
for (i = 2; i <= sublen; ++i)
{
while (j > 0 && substr[j + 1] != substr[i])
j = next1[j];
if (substr[j + 1] == substr[i])
++j;
next1[i] = j;
}
}

void getNext(char s[],int next[])
{
int length=strlen(s);
int i=0,j=-1;
next[0]=-1;
while(i<length)
{
if(j==-1||s[i]==s[j])
{
++i;
++j;
next[i]=j;
}
else
j=next[j];
}
}

Answer 1

这两种应该是一样的，书本上的是第二中求Next方法，还有一种改进的是对当 s[i]==s[j]时令
next[i]=next[j];这样可以减少边界情况下的比较次数; 针对第二种主要迷惑你的可能是j=next[j];
KMP算法本质上是个递推的过程，在求next时，它是只有模式串的又一次模式匹配，所以对 j=next[j] 这个递推，它既是在模式串中求next的过程，也是在模式串中进行模式匹配的过程;
在模式串的模式匹配时当第 j 个字符不匹配的时候跳到模式串中的下一个字符重新匹配，模式串中局部的模式匹配结果作为模式串与主串不匹配是要跳转的下个字符;
我擦，我自己都晕了，看看能不能帮你理解理解;
在实际的代码验证时要特别注意初始状态，即时那些 i j 的变量值是从 -1 ，0 ，1哪个开始的，一旦错了整个结果就错了，我在网上试了好多代码都不对，就是因为初始状态给错了

Answer 2

同样是推荐清华大学出版社的那个严蔚敏老奶奶的数据结构
但不是书是视频视频讲得更清楚~上网一搜就可以找到

Answer 3

这个问题，清华大学出版社的那个严蔚敏老奶奶的数据结构书上说的比较清楚。