老规矩，讲算法前，先说一道小问题吧
给你一个长串和短串，求短串在长串中出现的次数和位置。
设长串长度为len1,短串长度为len2。
如果len1*len2<=108，那就很简单了，直接暴力枚举以每个字符为开始的字符串是否匹配即可，复杂度为O(len1*len2);(是不是感觉太大了?)
如果将数据范围扩大到len1,len2<-106呢？
现在就开始介绍我们的KMP算法。
有了前面的问题，KMP要解决的是什么就自然出来了，KMP的复杂度达到的耸人听问的O(len1+len2)。
我们可以想想我们相对于暴力算法需要改进什么？
我们可以每一次失配(也就是匹配失败)的时候，不用每一次都从上一次的出发点只往后移动一个字符，可以跳啊！
我们可以预处理出每一次跳的位置来有利于节省复杂度啊。
这里我们就讲一讲怎么跳，以及怎么进行预处理。
1.怎么跳？
我们假设字符串为abaaba
我们如果在第二个a时失配了，我们应该怎么往前呢？
我们就可以可以把第一个a放在这一个位置继续匹配。
那么，如果是第四个a呢？
我们是不是就可以把第二个a放在这个位置呢？
大家可以看到，第最后一个字符到第三个a的字符串是aba，而第一个字符到第二个a的字符串是不是也是aba，它们不是一样的吗？
讲到这里，大家应该大概的明白了KMP是怎么跳的了吧。
我们记一个nxt数组，nxt[i]表示的是从第一个字符到第i个字符的最长前后缀的长度。看不懂没关系，举个例子。
假设字符串为abaaba
nxt[0]=0
nxt[1]=0(ab无前后缀）
nxt[2]=1(aba最长前后缀为a)
nxt[3]=1(abaa-----a)
nxt[4]=0(abaab--无)
nxt[5]=3(abaaba-aba)
2.初始化
问题来了，怎么用很少的时间复杂度来进行初始化呢？
很容易想到递推，怎么递推呢？
我们假设求出了前面的nxt，现在多了一个，我们就应该找一找了。
我们可以跳前一个位置的nxt，直到跳到一个位置后面有一个字符是所需要的，是那里的后面那一个字符。
每个这样递推就好了！
而查找的过程与初始化的过程类似，这里就不再赘述了。
下面上一份模板代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s1[],s2[];
int nxt[];
int main()
{
scanf("%s",s1);
scanf("%s",s2);
nxt[]=;
int len1=strlen(s1);
int len2=strlen(s2);
for(int i=,k=;i<len2;i++)
{
k=nxt[i-];
while(k>&&s2[k]!=s2[i]) k=nxt[k-];
if(s2[k]==s2[i]) k++;
nxt[i]=k;
}
for(int i=,j=;i<len1;i++)
{
while(j!=&&s1[i]!=s2[j]) j=nxt[j-];
if(s1[i]==s2[j]) j++;
if(j==len2)
{
printf("%d\n",i-j+);
}
}
for(int i=;i<len2;i++) printf("%d ",nxt[i]);
return ;
}
模板题：https://www.luogu.org/problemnew/show/3375
感谢大家的支持！
如果有不足之处，请尽管提出，本人不胜感激！