KMP

KMP算法是用来求这类问题：求子串a在字符串b中的个数。

索引：如果我们按照普通方法求这个问题就是一一比较，然后移一位再一一比较，，，这样的结果显示是超时，因此前辈们总结出一种算法，它可以不需要一位一位的移，有时候可以移好多位，这样就可以很快得出答案了。

在这个算法中我们首先要对子串a进行分析，子串一般是比较短的，我们定义一个同样大小的数组next，分别对应子串里的每一位，我们分析子串里各个字符前后的重复与否，进行记录。

分析的结果就是如果next数组里的数不等于0，则说明子串的前缀和后缀有重复。（前缀，后缀的定义不明白的可以问问度娘）

借用一下别人的例子说明：

 

所以求这个next数组是第一步，也很重要，它的模板为下边，不长，但灰常神奇，前辈们太厉害啊

void get_next(int pl)       //pl为子串的长度

{    int i=0,j=-1;

   next[0]=-1;

   while(i<pl)

{   if(j==-1||p[i]=p[j])    //p为子串

   {   i++;j++;

      next[i]=j;   }

   else

  j=next[i];

}

}

而KMP就是利用这个next数组来比较的，代码和next的模板类似，直接套着用：

int KMP(int pl,int sl)   //sl为字符串长度

{  int i=0,j=0,sum=0;

  get_next(pl);

 while(i<sl&&j<pl)            //s为字符串

{   if(j==-1||p[j]==s[i])

    {   i++;j++; }

    else

    j=next[j];

   if(j==pl)

   { sum++;j=next[j];}

}

return sum;

}

next+KMP就可以求出子串在母串中的个数了，接下来就是next数组其他应用：

1、求一个字符串中的循环串，next数组模板+以下代码：

求出next数组后，

for(i=1;i<=pl;i++)

{len=i-next[i];            //len位循环串长度

if(len!=i&&i%len==0)

cout<<len<<" "<<pl/len<<endl;     //求出循环串长度和循环次数

}

2、求一个字符串的前缀和后缀重复的长度，next数组模板+以下代码：

求出next数组后，

int j=0;

for(int i=pl;p[i]!=-1;)

{   sum[j++]=i;            //sum数组里存放的就是前后缀重复子串的长度，然后遍历sum数组输出就好了

    i=next[i];

}

next数组的应用，多理解理解，习题网址  ：http://acm.hust.edu.cn/vjudge/contest/121814#status
 密码nefu  

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有