KMP 学习笔记

符号规定

先来规定一些符号。

  1. \(\lvert S\rvert\) 代表这个字符串 \(S\) 的长度。
  2. \(S_{l\cdots r}\) 代表字符串从第 \(l\) 个字符到第 \(r\) 个字符组成的字串。
  3. \(F(S,i)\) 等同于 \(S_{1\cdots i}\)(就是字符串长度为 \(i\) 的前缀)
  4. \(E(S,i)\) 等同于 \(S_{\lvert S\rvert-i+1\cdots \lvert S\rvert}\) (就是字符串长度为 \(i\) 的后缀)注意在我们的定义里这个后缀是从左往右读的
  5. \(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;
}

热门相关:我有一个进化点   一等狂后:绝色驭兽师   我的黑月光女友   都市最强小村医   惊世第一妃:魔帝,宠上身!