KMP
KMP是一种字符串匹配算法，也可以叫它模式匹配算法。
作用大概是判断一个字符串 \(S \ ,len=n\) 是否是字符串 \(T \ ,len=m\) 的字串，并且找出 \(S\) 在 \(T\) 当中每一次出现的位置。
要使用这个算法必须先知道一个十分重要的思想：\(\text{next}\) 数组。
\(\text{next}\) 指针
在跑KMP之前需要对于 \(S\) 处理出这个东西（当然，这个东西会出现在很多字符串题里）。
它是一个类似于 AC 自动机的 \(\text{fail}\) 指针的东西（都是在失配时用来转移）。
但是 \(\text{next}_i\) 是求前缀 \(S[1,i]\) 的最长的 Border （同时为原串前缀和后缀的一个子串）。
AC 自动机的 \(\text{fail}\) 之后会说。
-
定义：\(\text{next}_{i}=\max\{j\ |\ S[1,j]=S[i-j+1,i] \ , j\le i\}\)
说白了，\(\text{next}_i\) 就是对于 \(S\) 的前缀 \(S[1,i]\) ，能够把这个前缀分成两个完全相等的部分 \(S[1\sim j]\) 和 \(S[i-j+1 \sim i]\) 的最大位置 \(j\)。
如果不存在这样子的 \(j\) ，那么 \(\text{next}_i=0\)。
为了方便叙述，定义这个满足条件 \(S[1,j]=S[i-j+1,i]\) 的 \(j\) 为 \(\text{next}_i\) 的"候选项"。
你可以使用朴素的 \(\text{O}(n^2)\)算法来计算，但是这很明显不够啊，我们还不如不用它，直接暴力匹配 \(S\) 和 \(T\) 得了。
那么这个时候就有一个引理：
若 \(j\) 是 \(\text{next}_i\) 的一个候选项，那么满足 \(j^\prime < j\) 的最大的 \(\text{next}_i\) 的"候选项" \(j^\prime\) 是 \(\text{next}_j\) 。
证明使用反证法+画图即可。
也就是说 \((\text{next}_j,j)\) 这个区间当中的数都不是 \(\text{next}_i\) 的“候选项”。
用它可以对求 \(\text{next}\) 的过程进行优化。
根据它可以发现，对于 \(\text{next}_i\) ，他的所有候选项是 \(\text{next}_i,\text{next}_{\text{next}_i},\text{next}_{\text{next}_{\text{next}_i}}...\)
然后又有一个引理2：
如果 \(j\) 是 \(\text{next}_i\) 的一个“候选项”，那么 \(j-1\) 一定是 \(\text{next}_{i-1}\) 的”候选项“。
因为如果 \(S[1,j]=S[i+j-1,i]\) ，那么肯定会有 \(S[1,j-1]=S[i+(j-1)-1,i]\) 。
（画图即可证明）
那么我们在计算完 \(\text{next}_{i-1}\) 之后，我们让 \(\text{next}_i\) 的所有候选项变成 \(\text{next}_{i-1}-1,\text{next}_{\text{next}_{i-1}}-1,\text{next}_{\text{next}_{\text{next}_{i-1}}}-1...\) 就可以了。
复杂度就变成了线性的。
实现
在有了 \(\text{next}\) 之后，我们完成了对 \(S\) 的自行匹配。
现在还需要做一个类似的过程，让 \(S\) 和 \(T\) 进行匹配。
我们定义 \(f_i=\max\{j \ | \ T[i-j+1,i]=S[1,j] \ ,j \le i\}\)。
如果 \(f_i=n\) 那么就证明，\(S\) 在 \(T\) 中出现了一次，并且它出现在区间 \(T[i-n+1,i]\)。
我们类比上面 \(\text{next}\) 的求法就能求出 \(f\)。
\(\text{next}\) 的求法说通俗点就是：
假设 \(\text{next}_{i-1}\) 已经求出来，那么尝试一直扩展这个 \(j\) ，
如果说下一个位置 \(j+1\) 无法满足 \(S[j+1]=S[i]\) ，那么令 \(j=\text{next}_j\) （失配），直到 \(j=0\) 再停止。
如果说下一个位置是满足要求的，那么令 \(j=j+1\)。
复杂度是 \(\text{O}(n+m)\)。
#include<bits/stdc++.h>
using namespace std;
const int si=1e6+10;
int n,m;
string s,t;
int Next[si],f[si];
int main(){
Next[1]=0;
cin>>s>>t;
n=(int)s.size(),m=(int)t.size();
s=' '+s,t=' '+t;
for(register int i=2,j=0;i<=n;++i){
while(j>0 && s[i]!=s[j+1]) j=Next[j];
if(s[i]==s[j+1]) ++j;
Next[i]=j;
}// calc next
for(register int i=1,j=0;i<=m;++i){
while(j>0 && (j==n || t[i]!=s[j+1])) j=Next[j]; // 这里把 j==n 放到里面了，有些要你求 Border 的题要提出来写（比如lg3375）
if(t[i]==s[j+1]) ++j;
f[i]=j;
if(f[i]==n){
// S exist in T.
}
}// calc f
}
AC自动机
咕咕咕
Reference
《算法竞赛进阶指南》