KMP算法，快速模式匹配算法，是在暴力匹配的基础上进行的优化。
给定两个串，一个称为主串，另一个称为模式串，我们要在主串里找到一个连续的字串和模式串匹配。
该算法通过一个next数组进行记录，从而优化指针的移位，降低时间复杂度。
对于不同的人对next的定义略有不同，但核心思想都是一样的，掌握KMP算法的思想尤为重要。
前置知识：前缀与后缀
一个字符串的前缀与后缀都是字符串。
如：ABCDEFG这个字符串，它的前缀和后缀字符串的长度是相同的，如下：
字符编号： A B C A B 0 1 2 3 4 长度：1 A B 长度：2 A B A B 长度：3 A B C C A B 长度：4 A B C A B C A B 长度：5 A B C A B A B C A B
对于模式串的next数组，就是要求每一个字符之前的字符串的前缀和后缀的最长匹配。
但是注意，我们这里使用一个静态的串来演示前缀和后缀，而在下面的计算中实际上是通过指针的移位实现一个动态变化，当匹配成功时前缀和后缀的长度都加一，指针向一个方向移动，而非向上面那样指针相向移动。
next数组
定义
next数组的下标和模式串字符下标是一一对应的，存储的值是 当前下标之前的字符串 的 前缀和后缀的最长匹配。
过程推演
暴力匹配
Step1 实时记录一个匹配长度len以及指向模式串和主串的指针
Step2 如果当前字符匹配，模式串和主串的指针以及长度len均+1
Step3 如果失配，则模式串的指针和len重置为0，然后重复Step2，直到再次失配，此时的len即为模式串和字串匹配的最长长度。
next数组优化
一些约定和解释
- 模式串当前指针指向的下标为i+1（即待匹配字符）
- len表示当前匹配成功的长度
- s1表示待匹配字符之前的字符串，这个字符串在主串里长度为len，在模式串中为s[0~i]
- 通过调用next[i+1]我们可以知道：对于s1，长度为next[i]的后缀和长度为next[i]的前缀是完全一样的，并且前缀字符串的结尾下标是next[i]-1。
过程
Step1 实时记录一个匹配长度len以及指向模式串和主串的指针
Step2 如果当前字符匹配，模式串和主串的指针以及长度len均+1
Step3 如果失配，“回溯“到对应的前缀字符串的末尾，len更新为next[i]，进行Step 4
Step4 前缀字符串的下一个字符与待匹配字符进行匹配，成功则重复Step 2，如果失配重复Step 3直至next数组的值为0.
next数组的使用及初始化
next[i]是待匹配字符的下标
next[i]-1表示前缀字符串的结尾
我们使用next数组目的是找到前缀字符串的下标，但因为next数组存储的是长度，我们在调用时next[i]-1表示前缀字符串的结尾，next[i]是待匹配字符的下标，在使用时需要注意。
当next[i]=0的时候即为没有任何匹配，我们需要提前初始化next[0]为0，表示无法匹配。
在其他的不同教程或者博客中，有些next数组的定义为前缀和后缀的最长匹配-1，即前缀字符串的结尾下标，两种定义大同小异，只需要使用上灵活处理即可。
计算next数组
回顾刚才的暴力算法，我们实时维护了一个len，如果模式串和主串都是同一个字符串，那么这个len就是 当前下标之前的字符串的前缀和后缀的最长匹配，也就是next数组的值。
既然是计算len，我们可以结合前面的next优化：我们在计算next数组的过程中可以通过next数组进行优化计算了，但是要注意初始化问题。
合理性分析：因为计算next数组只会向前移动去寻找next数组的值，假设当前计算next[i+1]，那我们只会用到next[0]~next[i]的值，而这些值均是已经计算出来的值。
结论：进行计算next数组的过程和进行字符串匹配的过程是一样的，区别在于计算next数组的模式串和主串是相同的，而匹配是两个不同字符串进行匹配。
实现步骤
我们可以设l和r两个指针，初始化为l=0,r=0，其中l-1代表最长匹配的结尾下标，l表示最长匹配长度，同时也代表待匹配字符，r表示待计算next的字符的下标。
判断s[l]是否等于s[r]来区分两种情况
继承最长匹配
如果相等则说明最长匹配可以拓展，则next[r]=next[l]+1此时l++和r++，继续判断下一位。
“回溯”寻找最长匹配
如果不相等则说明不匹配，需要向前“回溯”寻找匹配的字符串。
回溯过程实际上是l指针前移的过程，令l=next[l]来实现向前移动，直到s[l]==s[r]继承最长匹配，或者是l==0到无法继承next[r]=next[l]+1。
前移操作的合理性
因为待匹配字符之前的 模式串的前缀 和 主串的后缀 是相等的，因此，我们只需要判断前缀和后缀之后的一位是否相等即可。
我们的判断条件是s[l]==s[r]，l和r的意义上文已经解释了，可以发现l和r就是模式串的前缀和后缀的后一位。
代码实现
代码中l初始化为0，r初始化为1。
我们的目的是计算前缀和后缀字符串的最长匹配，如果将r初始化为0，因为next数组比较的两个串是一样的，最后会一直成功匹配，next成为一个递增的序列，而不是如我们想的一样得到最长匹配。
为此我们将r初始化为1，这样实际上是默认从一个长度为2的字符串开始匹配，直到找到第一个与前缀匹配的情况。
int next[N]={0};
void calnext(char s[])
{
int len=strlen(s);
int l=0,r=0;
for(r;r<len;r++)
{
while(l!=-1&&s[r]!=s[r])
{
l=next[l];
}//不停向前回溯的过程
if(s[r]==s[l])
{
l++;//如果最终都不匹配，则j不变仍为-1
}
next[r]=l;
}
}
r++放在了for里，l++因为只有匹配成功才会变化，所以放在了if里。
完整KMP算法实现
KMP算法的第一步是计算模式串的next数组，然后再进行匹配。
整体过程和next一样，但区别在于l和r的初始值，均为0，因为这里就是要找完全匹配，所以不需要特殊处理。
int next[N];
void cal_next(char s[]);
bool KMP(char text[],char s[])
{
cal_next(s);
int len=strlen(text);
int m=strlen(s);
int l=0;
for(int r=0;r<len;r++)
{
while(l&&text[r]!=s[l])
{
l=s[l];
}
if(text[r]=s[l])
{
l++;
}
if(l==m)
{
return 1;
}
}
return 0;
}
如果要统计模式串在字串中出现的次数，只需要增加一个cnt统计j==m的次数并返回这个次数即可。
注意，在进行cnt++之后j需要前移到next[j]，这是因为可能出现重叠的情况，如果不考虑重叠，让j=-1即可
参考内容：
[1]．
