欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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]的理解
KMP算法next数组的理解

这篇文章的思路来自:

https://www.cnblogs.com/dusf/p/kmp.html

相关标签: 算法学习