【算法漫笔001】KMP、exKMP

FeIndentOvO

2026-08-16 10:51:59

发布于：重庆

12阅读

0回复

0点赞

【算法漫笔】浅谈KMP算法、exKMP算法

KMP算法

KMP算法主要解决的是字符串匹配问题，即求一个字串在 $K$ 原串 $S$ 出现的最小位置。我们令 $S$ 的长度为 $N$ ， $K$ 的长度为 $M$ 。

Brute-Force

首先容易想到在字符串 $S$ 中查找子串 $K$ 的暴力匹配算法 Brute-Force，它的工作原理很简单，也就是一个一个比对字符，如果不匹配则跳过，直到匹配为止。其缺陷也很显然，如果 $K$ 的前 $M-1$ 位都能够匹配但最后一位无法匹配，该算法的时间复杂度可以来到 $O(NM)$ （如下图）。

这在 $N,M \le 10^5$ 的级别下显然是无法通过的。

优化

那么问题就来了，既然我们已经知道前 $M-1$ 的字符是匹配的，而第 $M$ 个字符是不匹配的，那我们能否通过这个信息在下一次匹配的时候跳过部分字符的匹配呢？显然的，我们可以跳过部分匹配，但跳过的字符数量又为多少呢？

next数组

让我们引入一个 $next$ 数组，其第 $next_i$ 表示在 $i$ 字符匹配失败时，可以跳过接下来的 $next_i$ 次匹配。这个数为多少呢？
我们定义 $next_i$ 为模式串 $K_{0,1,\dots,i-1}$ 中最长前后缀^[1]的长度。

此时容易发现，当匹配到 $K_j$ 失败时（即 $S_i \neq K_j$ ），我们已经成功匹配了 $K_{0,1,\dots,j-1}$ 。根据 $next_j$ 的定义， $K_{0,1,\dots,next_{j}-1}$ 与 $K[j-next_j,\dots,j-1]$ 完全相同，这意味着我们完全可以跳过这些已经匹配的内容。

不难发现，在使用 $next$ 数组跳过匹配内容时，所有匹配的内容仅匹配了 $1$ 次，假设我们构造 $next$ 数组的时间复杂度为 $O(M)$ ，那么我们的总时间复杂度为 $O(N+M)$ 。现在问题来了，我们怎么在 $O(N)$ 的时间下构造 $next$ 数组呢？

构造next数组

如何构造 $next$ 数组？换句话说，如何计算一段字符串的最长前后缀？

显然我们有暴力计算方法，显然可以用 $O(i)$ 的时间复杂度构造一个 $next_i$ ，于是乎构造整个 $next$ 的时间复杂度就来到了 $O(M^2)$ ，与 Brute-Force 算法无异，显然不行。

此时我们可以使用递推的方式计算，由于我们在计算 $next_i$ 时，知道 $next_{1,2,\dots,i-1}$ 的全部内容，所以我们实际上可以通过 $next_{1,2,\dots,i-1}$ 递推出 $next_i$ 。已知 $next_{i−1}$ ，看 $K_{i-1}$ 能否接在 $K_{next_i-1}$ 后面。能就向后继续暴力匹配更长的最长前后缀，否则就回退。如下：

next[0]=-1;
int i=0,j=-1;
while (i<M-1) {
	if (j==-1||K[i]==K[j]) {
		i++;
		j++;
		next[i]=j;
	}
	else {
		j=next[j];
	}
}

关于递推构造next数组的时间复杂度证明

显然的， $i$ 未曾回退，且 $next_j < j$ ，每次匹配成功时 $i$ 和 $j$ 同时加 $1$ ，而 $i$ 总共只增加了 $M−1$ 次，所以 $j$ 的总增加次数 $\le M$ 。

由于 $j$ 的初始值为 $-1$ ，且 $j \ge -1$ 恒成立， $j$ 的总减小次数 $\le$ 总增加次数 $+1 \le M$ 。

通过以上结论容易得到，全部在 else 分支中的构造时间复杂度为 $O(M)$ 。
全部在 if 中就更不用说了，显然 $i$ 会达到 $M-2$ ，时间复杂度仍为 $O(M)$ 。

因此，我们得出结论：构造 $next$ 数组的时间复杂度为 $O(M)$ 。根据前文内容，字符串匹配问题的时间复杂度来到了 $O(N+M)$ ，对比 Brute-Force 的 $O(N^2)$ 快了许多。

模板代码

void build_next(string K) {
	int M=K.size();
	next[0]=0;
	int j=0;
	for (int i=1;i<M;i++) {
		while (j>0&&K[i]!=K[j]) {
			j=next[j-1];
		}
		if (K[i]==K[j]) {
			j++;
		}
		next[i]=j;
	}
}
int kmp(string S,string K) {
	build_next(K);
	int i=0,j=0,N=S.size(),M=K.size();
	if (M==0) return 0;
	while (i<N&&j<M) {
		if (S[i]==K[j]) {
			i++;
			j++;
		}
		else if (j>0) {
			j=next[j-1];
		}
		else {
			i++;
		}
	}
	if (j==M) {
		return i-j;//K所在位置
	}
	return -1;//无法匹配
}

exKMP算法

exKMP，即 Z算法，事实上和 KMP 关系并不算太大。

Z数组

让我们引入一个数组 $Z$ ，其中 $z_i = \operatorname{LCP}$ ^[2] $(S,S_{i, \dots ,n-1})$ 。特别注意，我们令 $Z_0=0$ ，这样不仅不会影响算法正确性，反而可以便于我们实现。

构造Z数组

显然可以想到暴力匹配，时间复杂度 $O(N^2)$ ，显然不行。

考虑优化。

我们维护一个区间 $[l,r]$ ，称为 Z-box，其满足以下性质：

$S_{l,\dots,r}=S_{0,\dots,r-l}$

此时我们已经计算出 $Z_1, \dots ,Z_{i-1}$ ，现在要计算 $Z_{i}$ ，思考我们在优化构造 $next$ 数组时得到的启示，我们如何利用 $Z_1, \dots ,Z_{i-1}$ 的信息构造 $Z_i$ 呢？

我们可以先试着分类讨论：

$i > r$

显然， $i$ 在当前的 Z-box 之外，没有可用的已知信息，我们只能从 $i$ 开始暴力扩展。

此时扩展完成后，更新我们的Z-box：

$l = i, \ r = i + z[i] - 1。$

$i \le r$

$i$ 在当前的Z-box内部，这意味着我们可以利用已知信息。

尝试令 $k=i-l$ ，则 $i$ 在Z-box中对应的位置就是 $k$ 。

由于 $S_{l, \dots ,r}=S_{0, \dots ,r-l}$ ，因此 $S_{i, \dots ,r}$ 对应于 $S_{k, \dots ,r-l}$ 。

此时， $Z_k$ 已经计算过，它告诉我们 $S$ 与从 $k$ 开始的后缀的 $\operatorname{LCP}$ 长度。

那么此时如果 $Z_k<r-i+1$ ，说明 $S_{k ,\dots ,k+Z[k]-1}$ 完全落在对应的前缀范围内，可以直接取 $Z_i=Z_k$ 。

反之，如果 $Z_k \ge r-i+1$ ：说明匹配可能延伸到Z-box之外，我们无法直接确定。此时，我们令 $Z_i=r-i+1$ ，然后从该位置继续进行暴力扩展

扩展完成后，更新Z-box： $l=i,r=i+Z_i-1$ 。

即：

void build_Z(string s) {
	int n=s.size();
	int l=0,r=0;
	for (int i=1;i<n;i++) {
		if (i<=r) {
			z[i]=min(z[i-l],r-i+1);
		}
		while (i+z[i]<n&&s[z[i]]==s[i+z[i]]) {
			z[i]++;
		}
		if (i+z[i]-1>r) {
			l=i;
			r=i+z[i]-1;
		}
	}
}

时间复杂度证明

代码中唯一可能出现时间复杂度的问题是 while 循环。

由于只有 $r$ 向右扩展时，while 才会执行。每次成功的匹配都会使 $r$ 至少增加 $1$ ，而 $r$ 的取值范围是 $[0,n−1]$ ，因此 while 循环的总执行次数不会超过 $n$ 。

容易得到总时间复杂度为 $O(n)$

应用

通过构造一些特殊的字符串，使用 exKMP 将会直观的解决部分问题。

例如：我们令字符串 $T=S+c+K$ （我们令 $S$ 的长度为 $N$ ， $K$ 的长度为 $M$ ），其中 $c$ 为一个在 $S$ 和 $K$ 中都未出现的字符，例如 ^,&,# 等。

此时根据 $Z$ 函数的定义，如果 $Z_i=M$ ，则说明在 $S$ 的 $i-M-1$ 位置找到了一次 $S$ 对 $K$ 的匹配。其时间复杂度和 KMP 相同为 $O(N+M)$ 。

注释&致谢

感谢 StackEdit软件，欢迎大家去使用这个免费的 Markdown 编辑软件。它不仅可以在线使用，还可以下载使用。

$z_i = \operatorname{LCP}(S, S[i \dots n-1]) = \max\{ k \mid 0 \le k \le n-i \ \text{且}\ S[0 \dots k-1] = S[i \dots i+k-1] \}$

通俗来讲即是：从两个字符串的第一个字符开始，最多能连续匹配多少个字符。

最长前后缀：最长相等的前缀和后缀的长度，也就是字符串 $T$ 的前 $P$ 个字符和后 $P$ 个字符的最大 $P \neq T_{len}$ ，其中 $T_{len}$ 为 $T$ 的长度。 ↩︎
LCP，即最长公共前缀长度（Longest Common Prefix），其严格数学定义为： ↩︎