Question

KMP算法中的next数组如何计算

张乃孝上的
makenext(int c[],int *next)
{
int i=0,k=-1;
next[0]=-1;
int maxn=maxnum(p);//maxnum函数返回数组p的当前长度，在此略去
while(i<maxn-1)
{
while(k>=0&&c[i]!=c[k])k=next[k];
i++;k++;
next[i]=k;
}
}
但是理解不了什么意思。求讲解下，谢谢！

Answer 1

next[i]表示的是：
在第i个字符前面的i-1个字符里面，
从开头开始的1个字符与最后1个字符是否相等，若不是，则next[i]=0,否则继续看下面；
从开头开始的2个字符与最后2个字符是否相等，若不是，则next[i]=1,否则继续看下面；
从开头开始的3个字符与最后3个字符是否相等，若不是，则next[i]=2,否则继续看下面；
……
就是这样的判断取值。
它的意思就是如果到了某个字符不匹配的情况时候，你就可以直接把模式串拖到从开头开始的那next[i]个字符等于当前字符的前next[i]个字符的地方，这样就少了很多重复的无效的比较和移动。