前言
KMP 算法，全称 Knuth–Morris–Pratt 算法，其中使用了前缀函数，所以这篇一起讲了。
学完感觉偏简单，应该挺实用的。
使用场景
现在你有两个字符串，分别是长度为 n 的 str 和长度为 m 的 ptr 。
求解： str 中包含多少个为 ptr 的子串。
明显地，暴力求解时间复杂度为 O(nm) ，而 KMP 算法求解的复杂度为 O(n+m) 。
算法实现
KMP 算法分为两个部分，第一个是预处理 ptr 的前缀数组，第二个才是 KMP。
这里先设需要比较的两个字符串：
str = b a c b a b a b a d a b a b a c a m b a b a c a d d a b a b a c a
ptr = a b a b a c a
前缀数组
定义一个数组 next ,使 next_i 为以 ptr_i 为右边界的前缀的最大相同前后缀。
OK想必各位看完上面解释都很懵，下面为具体解释：
======================================================
以 ptr_i 为右边界的前缀，即 ptr_{1 \sim i} 这个子串。
其中，这个子串的最大相同前后缀可以这么理解：
设 k_i 为它的最大相同前后缀，则一定有 0 \le k_i < i ， ptr_{1 \sim k_i} = ptr_{i-k_i+1 \sim i} 。
再设 k_i < q_i < i ，则一定有 ptr_{1 \sim q_i} \ne ptr_{i-q_i+1 \sim i} 。
使 next_i=k_i 。
======================================================
代码：
void cal(){
int k=0;//初始长度为0
for(int i=2;i<=m;i++){//长度为1也是没有前后缀的
while(k>0 && b[k+1]!=b[i]) k=next[k];//回溯
if(b[k+1]==b[i]) k++;//相等最大值增加
next[i]=k;//存当前最大值
}
}
那么 next=0,0,1,2,3,0,1 。
肯定有同学对 k=next_k 这个回溯有问题，下面为我的证明：
======================================================
设现在的 ptr=aabaaa （那个当例子不好解释），
当 i=4 时， k=1 ，实际上我们现在的最大后缀就正是从 ptr_4 开始的，如果想增大 k ，我们肯定不能指望将后缀的左边界再向左移（因为这就是之前算过的 i 的情况），所以我们希望接下来 ptr_{k+1} = ptr_{i+1} （这里写 i+1 是对于这次循环，下一次循环 i 会自动增加所以去掉后面 +1 ），以便我们的最大值 k++ 。
当 i=6 时，明显地，通过上一轮计算得出的 k=2 ，这一轮我们 while 循环中比较的是 ptr_3 和 ptr_6 ，不相等。我们就要退而求其次，因为之前算过的更小的相同的前后缀中后缀在这里更新了，所以不起作用了，我们需要重新算。
当前 k=2 的情况是 ptr_4 为后缀的左边界，想要将它右移，我们就必须减小 k （因为 i 相当于当前字符串的大小，也就一定大于最大前后缀，也就是对于 next_i=k ，一定有 i>k ，这个式子的性质也是减小了 k ）。
现在我先让 p=4 ，也就是之前的左边界，我们知道的是 ptr_{1 \sim 1+k-1} = ptr_{p \sim i-1} ，所以 ptr_{p \sim i-1} 的最大前后缀也是 next_k ，那么所以 ptr_{1 \sim 1+k-1} 长度为 k 的前缀和 ptr_{p \sim i-1} 长度为 k 的后缀也是相等的，也就是 ptr_{1 \sim next_k} = ptr_{p+next_k-1 \sim i-1} 。
所以， next_k 就是目前转移 k 的最优方案。
======================================================
KMP
先上代码
void KMP(){
int k=0;//当前匹配串计算到的下标
for(int i=1;i<=n;i++){
while(k>0 && b[k+1]!=a[i]) k=next[k];//解释同上，都是取最优
if(b[k+1]==a[i]) k++;//相同就比较下一个
if(k==m){//有完全相同的子串
ans++;//子串数+1
k=0;
//i=i-m+2; 可以重复的话就回到之前遍历的地方
}
}
}
解释都写在上边了，应该很清楚了吧。
所以 KMP 理解了就很容易写出来了。
复杂度
假设匹配串里不存在重复的前后缀，即 next 中全是 0 ，那么每次移动其实就是一整个匹配串往前移动 m 个距离。然后重新比较，这样就比较 m 次，相当于比较 n 次， O(n) 复杂度。
前缀数组也差不多， O(m) 复杂度。
总体时间复杂度 O(n+m) ，空间复杂度 next 数组 O(m) 。
后记
这期耗了我 2 天时间，特别是证明 k=next_k ，真的很耗脑子，求点赞QWQ。
