符号规定
先来规定一些符号。
- \(\lvert S\rvert\) 代表这个字符串 \(S\) 的长度。
- \(S_{l\cdots r}\) 代表字符串从第 \(l\) 个字符到第 \(r\) 个字符组成的字串。
- \(F(S,i)\) 等同于 \(S_{1\cdots i}\)（就是字符串长度为 \(i\) 的前缀）
- \(E(S,i)\) 等同于 \(S_{\lvert S\rvert-i+1\cdots \lvert S\rvert}\) （就是字符串长度为 \(i\) 的后缀）注意在我们的定义里这个后缀是从左往右读的
- \(B(S)\) 表示 \(S\) 的一个最长 border 的长度（具体什么是 border 之后再谈）
前置芝士—border
定义
如果一个字符串 \(S\) 存在一个长度为 \(x\) 的 border，则有 \(F(S,x)=E(S,x)\)。也就是一个字符串的长度为 \(x\) 的前缀与长度为 \(x\) 的后缀相等。
例子
对于这个字符串：
\[\Large{qwertyqwertyqwerty} \]它的border有：
\[\textcolor{orange}{qwerty}qwertyqwerty \]\[qwertyqwerty\textcolor{orange}{qwerty} \]与
\[\textcolor{orange}{qwertyqwerty}qwerty \]\[qwerty\textcolor{orange}{qwertyqwerty} \]特别的，我们为了方便一般不认为一个完整的字符串是 border。
求法
对于一个字符串 \(S\)，我们一般会记录最大 border。我们只要能求出来最大 border 就可以求出所有的 border。这是因为border 是存在包含关系的。就比如上一个例子的第二个 border 实际上是基于第一个 border 的。
那我们考虑求法。设 \(\pi_i\) 代表 \(B(F(S,i))\)，即 \(S\) 的长度为 \(i\) 的前缀的最长 border。
KMP 发现 \(\pi\) 是可以被递推的。
我们目前假设知道了 \(\pi_{1\cdots i}\)，现在要求 \(\pi_{i+1}\)。
有一个结论：\(\pi_{i+1}\) 一定是 \(\pi_{1\cdots i}\) 中的一个 \(+1\)。因为它只有前面是 border 了之后才能拼上。
那么我们不妨设一个 \(f(x,c)\) 代表目前 \(F(S,x)\) 是一个 border 的前缀，然后我们考虑它所属的 border 能否匹配上 \(c\) 这个字符。
我们先给出 \(f\) 的递归逻辑，之后再解释。
\[f(x,c)= \left\{ \begin{array}{l} x+1 \space\space\space(S_{x+1}=c)\\ 0\space\space\space\space\space\space\space\space\space\space(x=0)\\ f(\pi_x,c)\\ \end{array} \right. \]\[\pi_i=f(\pi_{i-1},S_i) \]首先解释最简单的 \(0\)，这是因为如果当前能匹配的已经没有了，然后上面那个能够匹配的东西又不符合，所以就没有更小的原来的 border 用来匹配了。所以就返回 \(0\)。
然后的话我们先来从一开始看一下一幅图：
这就是我们的初始状态。因为 border 的性质两个绿色部分是完全一样的，所以我们一开始判断的就是黄色是否等于蓝色，如果是的话显然这就是一个新的 border，然后因为 \(\pi_{i-1}\) 就是之前最长的了，所以显然满足 \(\pi_i\) 性质，直接更新。
否则的话我们根据递归就是判断下面这幅图：
这个时候很神奇的事情就发生了，根据 border 性质，四个紫色部分显然是一样的，那么还是判断黄色和蓝色的就行了。因为一定有一个紫色在开头，还有一个紧挨着蓝色。然后紫色也一定是最长的次大，所以在绿色不满足性质的情况下它仍然是满足 \(\pi\) 的性质的。然后就愉快的求完了。
KMP
KMP 算法是一种用 \(O(\lvert S\rvert)\) 的时间复杂度来求出模式串 \(T\) 在文本串 \(S\) 中的所有出现位置的算法。
算法流程
我们先对于 \(T\) 求出 \(\pi\),也就是知道了所有的 \(B(F(T,i))\)。
然后开始匹配。我们首先枚举 \(S_i\),并记录 \(l\) 满足 \(T_{1\cdots l}=S_{i-l+1\cdots i}\)。显然如果 \(l=\lvert T\rvert\) 则 \(S_{i-l+1\cdots i}=T\)，也就是匹配成功一次。那么关键在于我们怎么线性维护这个 \(l\)。
先说结论：直接让 \(l=f(l,S_i)\) 即可。
对于这样一幅图，你会发现它就是答案。首先合法性肯定可以理解，因为每一个相同颜色的部分根据 border 性质显然是一样的，不过多解释。至于最优性，你会考虑深蓝色部分为什么不可以再延伸，这是因为如果可以再向左延伸，又因为 \(S\) 需要包含前面的，则 border 也会变得更长，不符合 \(f\) 的定义，矛盾。所以直接这么求即可。
例题
P3375 【模板】KMP
题目大意
给出两个字符串 \(s_1\) 和 \(s_2\)，若 \(s_1\) 的区间 \([l, r]\) 子串与 \(s_2\) 完全相同，则称 \(s_2\) 在 \(s_1\) 中出现了，其出现位置为 \(l\)。
现在请你求出 \(s_2\) 在 \(s_1\) 中所有出现的位置。
\(1 \leq |s_1|,|s_2| \leq 10^6\)，\(s_1, s_2\) 中均只含大写英文字母。
解法
kmp 模版，参考上方解法。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=1e6+5;
string s,t;
ll n,m;
ll pi[MAXN];
ll find_next(ll ed,char need) {
if(t[ed+1]==need) {
return ed+1;
}
return ed==0?0:find_next(pi[ed],need);
}
void kmp() {
for (int i=2;i<=m;++i) {
pi[i]=find_next(pi[i-1],t[i]);
}
}
void find() {
ll j=0;
for (int i=1;i<=n;++i) {
j=find_next(j,s[i]);
if(j==m) {
cout<<i-m+1<<endl;
j=pi[j];
}
}
}
int main() {
cin>>s>>t;
n=s.size(),m=t.size();
s=" "+s;
t=" "+t;
kmp();
find();
for (int i=1;i<=m;++i) {
cout<<pi[i]<<" ";
}
return 0;
}