Question

谁能解释数据结构中KMP算法的next函数?

比如一个待匹配的子串str[]="abaabc",给出每个字符的next是几,为什么?千万别贴大段的东西,用自己的话说.
晨之子:怎么算的?

Answer 1

假如str的前j个字符是前i个字符的后缀(j<i),那么next[i]就是所有这样的j的最大值
形象地说,就是假如第i+1个字符匹配失败之后,下一个可能匹配位置至少应该往后挪动多少

就"abaabc"而言
next[1]=0
next[2]=0
next[3]=1
next[4]=1
next[5]=2
next[6]=0

计算过程基本上抄自算法导论,假设str长度为n
k=0;//k表示当前匹配了多少位
next[1]=0;
for (i=1;i<n;i++)
{
while (k && str[i]!=str[k]) k=next[k];
if (str[i]==str[k]) k++;
next[i+1]=k;
}

之后计算str和某个长度为m的字符串text匹配的过程基本上是一样的
k=0;//用于记录str最长能够有前k位是text的前i+1个字符的后缀
for (i=0;i<m;i++)
{
while (k && text[i]!=str[k]) k=next[k];//发现不能匹配的时候就把str往后挪
if (text[i]==str[k]) k++;
if (k==n) printf("在位置%d处找到一个匹配\n",i+1-n);
}

对照着后面这一段很容易理解第一段