KMP算法简介
算法来源
Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。
主要作用
KMP 算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。
时间复杂度
$$ O(n+m) $$
$ n,m $分别表示字符串$ s_1,s_2 $的长度。
举例
两个字符串 $ s_1,s_2 $，$ s_1 $ 是文本串， $ s_2 $ 是一个模式串，要查找在$ s_1 $中$ s_2 $ 出现的位置。
方法1：暴力匹配
设$ i,j $分别为字符串$ s_1,s_2 $的指针，$ s1[i],s2[j] $分别表示字符串$ s_1 $和$ s_2 $当前正在比较的两个字符。
从$ 1 $ 到字符串$ s_1 $长度 $ len_{s1} $ 依次枚举，每枚举文本串的一个字符，就将 $ j $ 从 $ 1 $到字符串长度 $ len_{s2} $ 依次枚举，当s1[i]==s2[j]时，将i++,j++;，当a[i]!=a[j]时，令i=i-(j-1),j=0;，所以总的复杂度为 $ O(len_{s1} len_{s2}) $
方法二：KMP算法
这种算法的时间复杂度为 $ O(n+m) $，比暴力算法优化了很多，具体的解释如下。
KMP算法的原理
基本原理
首先假设当前的字符串$ s_1 $枚举到了第 $ i $ 位，字符串 $ s_2 $ 枚举到了第 $ j $ 位。当第$ s1[i] $ 与$ s2[j+1] $ 相同时，继续i++,j++;，当两个字符失配时（即两个字符不相等的时候），将j跳回为$ next[j] $（什么是$ next[] $数组，后文会详细讲解，粗略解释为是重新开始字符串匹配的最佳位置，以省去暴力枚举的时间），也就是退回了$ j-next[j] $个位置，并重新开始匹配。
$ next[] $数组
作用
$ next[i] $ 表示在模式串中，在第$ i $个位置失配时，需要重新匹配的起点。而这个重新匹配的起点是什么？
定义一个字符串$s$的border为$s $的一个非 s 本身的子串$ t$，满足$ t $既是$ s $的前缀，又是$ s $的后缀。对于$ s_2$，其每个长度为 $i$ 前缀$ s' $的最长 border $ t' $的长度就是$next[i]$的值。假如说我的模式串为 $ a,b,c,a,b $ ，那么$ next[3]=0,next[4]=1,next[5]=2 $，因为当$ i=3 $时，没有相同的前缀与后缀，当$ i=4 $时，相同的前缀与后缀为 $ a $，长度为$ 1 $，当$ i=5 $ 时，相同的最长的前缀与后缀为 $ a,b $长度为$ 2 $ 。那么当我们在第$ j+1 $位失配时，要回到第$ next[j] $位，因为此时我们将位置跳回了 $ next[j] $的位置后，模式串前面的字符对应关系没有改变，因为他们的后缀与前缀是相同的，改变的是后面的要比较的字符，而这种方法有恰好避免了漏掉字符串的问题，因为后缀都没有对应，整个字符串更是无法对应。如果还不能理解，如图：
举例来说，有一个字符串 $s_1=$ BBC ABCDAB ABCDABCDABDE，判断里面是否包含另一个字符串 $ s_2 = $ABCDABD？
1、首先，用$ s_1 $的第一个字符和$ s_2$的第一个字符去比较，不符合，关键词向后移动一位。
2、重复第一步，还是不符合，再后移。
3、一直重复，直到$ s_1 $有一个字符与$ s_2 $的第一个字符符合为止。
4、接着比较字符串和搜索词的下一个字符，还是符合。
5、遇到$ s_1 $有一个字符与$ s_2 $对应的字符不符合。
6、这时候想到的是继续遍历$ s_1 $的下一个字符，重复第1步。
7、其实这是很不明智的，因为此时 ABCDAB 已经比较过了，没有必要再做重复的工作，一个基本事实是，当空格与 D不匹配时，你其实知道前面六个字符是ABCDAB。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置“移回已经比较过的位置，继续把他向后移，这样就提高了效率。而帮助我们移动到最合适的位置的，就是$ next[i] $数组，这就是这个数组的作用。
8、已知空格与D不匹配时，前面六个字符ABCDAB是匹配的。查表可知，最后一个匹配字符B对应的部分匹配值”为$2$，因此我们只需要让模式串$ s_2 $的下标移动到对应下标为$2$的位置，也就是C，此时$ s_1 $的下标还是保持不变，在空格处，这样就避免了$ s_1 $下标回溯到第$6$步了，这样就大大减少了$ s_1 $的比较次数。
9、因为空格与Ｃ不匹配，搜索词还要继续往后移。这时已匹配的字符串为AB，最后一个匹配字符B对应的”部分匹配值”为$0$。因此我们只需要让模式串$s_2$的下标移动到对应下标为0的位置，也就是A，此时$ s_1 $的下标还是保持不变。
10、因为空格与A不匹配，并且此时并没有匹配的字符，因此只能继续后移一位。
11、然后逐位比较，直到发现C与D不匹配。
12、因为C与D不匹配，这时已匹配的字符串为ABCDAB，最后一个匹配字符B对应的”部分匹配值”为$2$。因此我们只需要让模式串$s_2$的下标移动到对应下标为$2$的位置，也就是C，此时$s_1$的下标还是保持不变。
13、然后逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。
这就是$ next[] $ 数组的作用。
构建
$ next[i] $数组的初始状态为$ next[0]=next[1]=0 $因为当字符串中没有或者是只有一个字符的时候，除了它的本身，不会再有其他的前缀或者后缀，所以它们的值自然为$ 0 $。然后，我们从$ 1 $ 开始枚举$ s_2 $，设$ j $ 表示正在处理的前缀的位置，当s2[j+1]==s2[i]时，即下一位能够与i相匹配，则j++，当两个不能匹配的时候时，将$ j $跳回到$ next[j] $,原理与上面类似，但是我们的目的是要保证前缀与后缀相同，然后继续枚举，如果$ j $ 调回后仍然与后缀对不上，那么我们将$ j $再次跳回，直到满足s2[j+1]==s2[i]或者是j==0，即跳回了最初的位置，说明没有前缀与后缀相同。最后将$ next[i] $赋值为 $ j $。
$ next[] $数组代码
scanf("%s",s1+1);
scanf("%s",s2+1);
int len1=strlen(s1+1),len2=strlen(s2+1),j=0;
nxt[0]=nxt[1]=0;//注意初始化
for(int i=2;i<=len2;i++)
{
while(j&&s2[j+1]!=s2[i])//字符串内部失配时，将前缀指针调整到上一个与它匹配的位置
j=nxt[j];
if(s2[j+1]==s2[i])//如果能匹配，将指针后移
j++;
nxt[i]=j;
}搜索
按照上面的方法比较即可。详情看代码注释：
搜索代码
for(int i=1,j=0;i<=len1;i++)
{
while(s1[i]!=s2[j+1]&&j)//对比字符串s1和s2，如果失配就将j跳回到next[j]
j=nxt[j];
if(s1[i]==s2[j+1])//如果成功匹配，就匹配下一位
j++;
if(j==len2)
{
printf("%d\n",i-len2+1);//完全匹配后，输出此时字符串s1的初始位置。
j=nxt[j];//向后移动一位，重新开始寻找
}
}代码
Fast命名空间中包括快读、快输、各种宏定义，不会影响代码阅读，您可以在左侧栏文章《代码模板》中查看具体内容。
#include<bits/stdc++.h>
using namespace std;
namespace Fast{...}
using namespace Fast;
char s1[M],s2[M];
int nxt[M],len1,len2;
int main(){
scanf("%s%s",s1+1,s2+1);
len1=strlen(s1+1),len2=strlen(s2+1);
int j=0;
for(int i=2;i<=len2;i++){
while(j&&s2[j+1]!=s2[i])
j=nxt[j];
if(s2[j+1]==s2[i])
j++;
nxt[i]=j;
}
j=0;
for(int i=1;i<=len1;i++){
while(j&&s2[j+1]!=s1[i])
j=nxt[j];
if(s2[j+1]==s1[i])
j++;
if(j==len2){
print(i-len2+1);
enter;
j=nxt[j];
}
}
for(int i=1;i<=len2;i++){
print(nxt[i]);
space;
}
return 0;
}
