目录
一、KMP是什么？
二、原理
1.思路
2.预处理
3.借助nxt实现字符串匹配
总结
一、KMP是什么？
烤馍片KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。KMP算法的时间复杂度为O(m+n) 。
二、原理
1.思路
首先想到的一定是无脑暴力质朴做法，从每一个元素开始搜，但是这样做在不友好的数据下复杂度能达到O(m*n)，这肯定会T起飞的。那么该怎么优化呢？思考在我们暴力做法中，有哪些是重复进行的？
我们拿一个样例手玩一下就懂了：
模式串：abcabc 文本串：abcabdababcabc
先质质朴思路，从前往后搜索...abcab..诶好的下一个c和d没有对上，那么按照不太聪明的质朴算法，我们是不是要往右一位重新开始匹配？但是聪明的小朋友们仔细观察一下，在我们已经搜索过的abcab中，是不是往右移3步即移动到末尾的ab时才能继续匹配？那我们就记录下来我们的相同的前后缀abc，这样我们能直接从前一个abc跳到下一个。这就是KMP思路的精髓，在匹配失败后不会一步一步的往后搜，而是利用已经搜过的过程中找到一个公共前后缀开始搜。
2.预处理
那么如何寻找前后缀呢？如果没有公共前后缀又该怎么处理呢？因此，我们需要预处理一个nxt数组出来。nxt表示什么？怎么处理？
char a[1000005],b[1000005];//在A中查找B
int n,m,nxt[1000005];//m是b串的长度
//nxt[i]表示不同时i指针的下一个位置
void Make_ST(){
//预处理较短的B显然可以减少时间复杂度并且较为灵活
int j=0;
nxt[1]=0;
for(int i=2;i<=m;i++){
while(b[i]!=b[j+1]&&j>0)j=nxt[j];
if(b[i]==b[j+1]){
j++;
nxt[i]=j;
}
}
}
nxt数组其实相当于一个路标，告诉我们如果在i位置出问题了，我们该回溯到哪里开始下一轮搜索，记录之前的努力，即nxt[i]。拿一个相对好说明的字符串举例，abcabcabcd。借鉴上面的代码段，我们发现第一个abc时j+1与i没有匹配成功，当第二个abc出现时他的nxt值是匹配到的与自己相同的字符串的结尾的指针，当第三个abc时匹配到的时第二个abc。那么当出现一个d时会发生什么？由于abc前半部分相同，我们不想浪费搜索这段的时间，所以我们需要往回跳，跳到前一个abc去，因为前一个abc的后面有可能存在d。由于之前标记，如果没有找到存在d的abc，指针很快会跳到0，时间无需担心。
3.借助nxt实现字符串匹配
即KMP算法。代码如下：
void Kmp(){
int j=0,ans=0;
for(int i=1;i<=n;i++){
while(j>0&&(j==m||a[i]!=b[j+1]))
j=nxt[j];//j>0为终止条件，j==m找到完整B，不等于跳过
if(a[i]==b[j+1])j++;
f[i]=j;
}
for(int i=1;i<=n;i++){
if(f[i]==m)ans++;
}
printf("%d",ans);
}
j代表匹配成功长度，如果当前位成功，j++;如果不匹配，这里用了一个f数组记录a数组中的每个元素对应b数组的第几位，如果对应m(末位)，代表有一个成功匹配的，ans++。
可能不太能懂？我手绘一下这个过程：
对于B串，我们已经经过预处理，找到了公共前后缀，如下图所示，颜色相同的部分都相同
那么当我们匹配成功时 正常向后，匹配失败时 便用nxt[i]跳跃到相同的前缀，下图为失配时的i,j,nxt[j]。
观察发现，，下图紫色方椭圆部分相同，所以直接跳跃是没有问题的。
如果下一步再出现问题，就在此以相同方式跳跃。这样我们就节省下了一步一步挪动的时间。
总结
KMP算法即为以巧妙的方法进行移动、回溯的算法，通过预处理，使我们之前搜索过的东西有了意义，可以快捷的进行字符串检索。
放几个经典例题：
P3375 【模板】KMP字符串匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
P5410 【模板】扩展 KMP（Z 函数） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
我滴任务完成啦！！！
