本文主要向大家介绍了C/C++知识点之KMP，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

 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];
} 
   

本文由职坐标整理并发布，了解更多内容，请关注职坐标编程语言C/C+频道！