目录
一：什么是KMP算法：
KMP算法是一种字符串查找算法，其核心作用就是在一个较长的字符串S中查找一个较短的字符串P，若S的长度为n，P的长度为m，那么仅仅用暴力算法匹配的话时间复杂度就是O（n*m），要优化就要用到KMP算法。
二：KMP算法思想及实现
分析：
我们由暴力匹配算法可以知道；我们每次都要从S串中的第i个元素开始进行对p的匹配，，如果匹配不成功就要再次返回到i+1的地方从头开始匹配。
如果我们能够减少往回走的距离，那么就相当于减少了匹配所需要的时间，KMP算法就是解决这个问题的。
我们先给出KMP算法的实现再研究其正确性。
假设我们某次从S串的第i个元素开始匹配，j为匹配成功的次数，匹配到i+j及以前都是匹配成功的，但是匹配到i+j+1的时候不成功，那么我们就尝试移动j，使得在S串i+j位置之前的一段是成功匹配的，那么我们就可以从i+j+1的位置开始进行匹配，就不用向前移动i从头开始了。
上图解释：
绿色箭头到绿色线之间是匹配好了的，我们把移动j类比成移动P串，移动的目的就是使得在蓝色线和绿色线之间的一段中，移动后的P串是与S串相匹配的，然后我们只需要在灰色箭头开始匹配就可以了，而不是从i+1的位置开始重新匹配。
那么就有个问题：j是如何移动的，怎么知道j要移动到什么位置？
我么用一个next数组存储j要移动到的位置，next[j]就是目标位置，就是移动的最短的，并且能够使得移动后的与移动之前的一段相匹配的位置。
如图：
那么next数组实际上存的东西就是j点之前的一段，和从头开始的一段，两段相匹配的从头开始那一段的末尾的位置，而且是离j最近的。
如何获得next数组：next数组的获得思想是和前面移动j的思想是一样的，就是相当于拿两个P串来匹配，这里我们就要给出没有某点不能再移动的解决方案：next[j]==0
代码实现：
#include<iostream>
using namespace std;
const int N=1e6+10;
char s[N],p[N];
int ne[N];
int n,m;//S串长度m，P串长度n
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>p[i];
cin>>m;
for(int i=1;i<=m;i++)
cin>>s[i];
for(int i=2,j=0;i<=n;i++)
{
//j表示为匹配成功的个数，就是i-j+1到i是匹配成功的
while(j&&p[i]!=p[j+1]) j=ne[j];//当前位置匹配成功次数大于0并且下一个位置不匹配的时候
//j就往后退
if(p[i]==p[j+1]) j++;//匹配成功就将匹配成功个数加1
ne[i]=j;//ne中存储的就是当前位置的匹配成功的个数
}
for(int i=1,j=0;i<=m;i++)
{
//当j为0的时候就是不能再移动的时候，就要从当前位置从头开始匹配了
while(j&&p[j+1]!=s[i]) j=ne[j];//这是往后退的实现
if(s[i]==p[j+1]) j++;//当前元素匹配成功就次数加1
if(j==n)//如果匹配完全成功就输出成功的串的开头位置
{
printf("%d ",i-n);
j=ne[j];
}
}
}写在最后：
由于本人目前还是蒟蒻，且由于文章只能用文字描述的局限性，所以本人自我觉得文章颇有漏洞或模糊之处，大家可以在评论区指出，如果有什么问题也可以在评论区提出，而且CSDN社区也有一些更为详尽的关于KMP算法的文章，例如：从头到尾彻底理解KMP（2014年8月22日版）_v_JULY_v的博客-CSDN博客_从头到尾彻底理解kmpzzz
这篇大佬的文章的长度大概足足有本篇的十倍之多，内容非常详尽，十分推荐。