KMP算法next数组的理解
程序员文章站
2022-03-31 21:17:36
...
void Getnext(int next[],String t)
{
int j=0,k=-1;
//k代表着前面的最大匹配字符数,-1是next[0]的意思
next[0]=-1;
while(j<t.length-1)
{
if(k == -1 || t[j] == t[k])
//此条件其实包含了两种情况:①k=-1表示所有前缀都不匹配,我们给他记为0 ②可以增长一个匹配,next[++j] = ++k;
{
j++;k++;
next[j] = k;
}
else k = next[k];//这个语句是精髓所在,表示:不能增长,需要减少匹配数
}
}
实际上,我们的目的是用数学归纳法,来求解next数组的每个值。当前已经求到next[j],接着就应该求解next[j+1],此时就分两种情况,一种是:重复的字符串个数会增加,即所谓的p[k]=p[j],此时p[j+1]=k+1;即p[++j]=++k;另一种就是不能增加,也就是说P[k]!=P[j],(TRU:其实还有一种,也就是k=-1,重复字符数不能再减少)即最大重复子串的长度不能增加了;按照next[j]的定义,就是当子串的第j位和主串的第i位不一致时,下一次,和主串i位进行比较的子串的j指针的位置。
对:k=next[k]的理解
这篇文章的思路来自:
https://www.cnblogs.com/dusf/p/kmp.html
上一篇: 容易理解的KMP算法next数组求法详解