符号规定
先来规定一些符号。
- \(\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 模版，参考上方解法。
代码
#includeusing 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<>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;}CF126B Password题目大意
给出字符串 \(S\)，你需要找到既是 \(S\) 的前缀又是 \(S\) 的后缀同时又在 \(S\) 中间出现过的最长子串。
\(1\leq \lvert S\rvert \leq 10^6\)
解法
首先显然要求出来关于 \(S\) 的 border 数组 \(\pi\)。
然后我们如果要求出 \(S\) 的所有 border 的话只需要不断求 \(\Large{\pi_{\pi_{\cdots_{\pi_{\lvert S\rvert}}}}}\)。因为 border 存在包含关系。
之后我们只要判断这个子串是否在中间出现过就行了。如果 \(S\) 中出现过一个长度为 \(k\) 的 border 则 \(\exists\pi_i=k,i\in[2,\lvert S\rvert-1]\)。所以我们求 \(m=\max(\pi_i),i\in[2,\lvert S\rvert-1]\)。然后我们一直迭代 \(S\) 的 border 直到当前的长度 小于 \(m\) 就停。因为存在包含关系所以一定可以。那么把这个 border 输出即可。
代码
#include#define endl '\n'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);}ll ans;void kmp(){for(int i=2;i>t;m=t.size();t=" "+t; kmp();ll ma=0;for(int i=1;ima){ans=pi[ans];}if(ans==0){cout<<"Just a legend"<<endl;}else{string A;for(int i=1;i<=ans;++i){A+=t[i];}cout<<A<<endl;}return 0;}