tip:以下内容仅本人理解，如有问题，欢迎指出
前言（？
首先我们要知道KMP是干嘛的
KMP 是一个字符串匹配算法，相当于AC自动机的弱化版，如果你完全理解了 KMP 和 Trie树 的话，那你也离学会AC自动机不远了
对于字符串匹配，我们有一个字符串和一个模式串，需要求字符串的子串里有没有这个模式串。例如：
mobaiawa <-字符串
awa <-模式串
它俩对齐的位置使字符串相应部分与模式串完全相同，这样的情况我们叫做匹配
在这里，我们只考虑一个字符串匹配一个模式串的情况
先丢一个暴力板子
for(int i=1;i<=n-m+1;i++){
bool flag=1;
for(int j=0;j<m;j++){
if(a[i+j]!=b[j+1]){
flag=0;
break;
}
}
if(flag){
//匹配成功，操作
}
}
手模 / 交一份代码可以发现大量的时间耗费在了最初的几个字母匹配上，于是，KMP 应运而生。
大致思想：
举个例子，字符串：abcababaaabcababc，模式串：abcababc
那么我们就可以进行操作：
abcabab|a|aabcababc
abcabab|c|
^ 在这失配
那么我们根据贪心，直接将匹配成功的子串的等于相同长度后缀的最大前缀“拽”过来（可能说不太清楚，看操作吧）
abcab|ab| //(匹配成功的子串)
|ab|cabab
ab为那个最大前缀
abcab|ab|aaabcababc
|ab|cababc //“拽”过来
abcab|ab|c //原来在这
可以证明中间的都不用操作，但我太蒟蒻了，不会证明，总之这个算法就是大幅优化了失配后重新配对的时间，防止大量无意义的失配，至于配对，还是得一个一个比。
这样，就可以大幅优化原来的暴力算法了。
获得这个信息的方法，就是KMP的预处理。
预处理
这个预处理是基于一个十分神奇的思路实现的，
暴力肯定是枚举前缀判定，但，我们可以不这么做。
先上代码
next[0]=next[1]=0;
for(int i=1,j=0;i<=l;i++){
while(j&&s[i]!=s[j+1])j=next[j];
if(s[i]==s[j+1])j++;
next[i]=j;
}
还是那句话，思路十分神奇。
换个例子：abcabcabcdabc
首先，抛开 while 不谈，那么这就是一个错误的暴力写法。
next[1] 无意义，毕竟只有一个的字符串的前缀永远等于ta的后缀。
所以，如果第一个就失配，直接从头开始
然后 next[i]=j 就说明了已经处理完了前 i 个前缀子串的问题了
又已知，j<=i 即过到的子串信息都已经处理好了
那么 我们就是在拿这个串做一个类似 KMP 的操作嘛
比如，过到这了：
abcabcabc|d|abc
abcabc|a|bcdabc
^ 这里失配了，i=10,j=6
那么 10 之前的 next[i] 早就处理好了，直接用（因为相当于匹配后缀嘛）
那么 next[6]=3 也就是跳到了这样的匹配情况：
abcabc|abc|dabc
|abc|abcabcdabc //跳/“拽”到这了
abc|abc|abcdabc //原来在这
^ j 指向这个位置，视觉上看起来像是字符串挪动了，但代码上是 j 的位置移动
也许应该这样？：
abcabcabcdabc //j 原来在这
^ j的位置
abcabcabcdabc // j 跳/“拽”到这了
^ j 的位置
abcabcabcdabc//匹配到这了
^ i 的位置
对齐 i , j+1 （因为永远是判断串的下一位能否匹配）：
abcabcabcdabc
abcabcabcdabc
^ j 的位置
然而 s[i] 仍然不等于 s[j+1] ，所以继续跳next[j]，直到跳到头（没有前缀，j==0 ）为止
然后就继续愉快地匹配，看以第 i 个字符为结尾的后缀字符串能否有前缀字符串匹配啦
*预处理结束
查找
上面已经讲的很清楚了就不多讲啦（逃
for(int i=1;i<=n;i++){//s2 是模式串
while(j&&s1[i]!=s2[j+1])j=next[j];
if(s1[i]==s2[j+1])j++;
if(j==m){
//匹配成功，操作
j=next[j];//继续匹配
}
}