菜王的 blog

记号

设模式串 $A$ 长度为 $n$，主串 $B$ 长度为 $m$。

设 $S[l, r]$ 为字符串 $S$ 从第 $l$ 位到第 $r$ 位构成的字串。

满足 $next_i$ 的条件但不一定最大的 $j$ 被称为 $next_i$ 的候选项。

KMP 算法，又称模式匹配算法，可以在线性时间内判断字符串 $A$ 是否是字符串 $B$ 的子串，还可以查找 $A$ 在 $B$ 中出现的位置。

KMP 算法分为两步：

1. 对 $A$ 进行自我匹配，求出数组 $next$，其中 $next_i$ 是满足 $next_i < i$ 且满足 $A[1, next_i] = A[i - next_i + 1, i]$ 的最大值（特别的，如果不存在 $next_i$，则 $next_i = 0$）。
2. 将 $A$ 与 $B$ 进行匹配，求出数组 $f$，其中 $f_i$ 是满足 $f_i \le i$ 且满足 $A[1, f_i] = B[i - f_i + 1, i]$ 的最大值。

显然当 $f_i = n$ 时 $A$ 在 $B$ 中的第 $i - n + 1$ 位开始出现了一次。

$next$ 怎么求呢？

首先，有一个引理：若 $j_0$ 是 $next_i$ 的一个候选项，那 $< j_0$ 的最大的 $next_i$ 的候选项是 $next_{j_0}$。

证明

先证 $next_{j_0}$ 是 $next_i$ 的候选项。

因为 $A[1, j_0] = A[i - j_0 + 1, i]$，同时取后 $next_{j_0}$ 个字符得 $A[j_0 - next_{j_0} + 1, j_0] = A[i - next_{j_0} + 1, i]$。

因为 $A[1, next_{j_0}] = A[j_0 - next_{j_0} + 1, j_0]$，所以根据 $A[j_0 - next_{j_0} + 1, j_0] = A[i - next_{j_0} + 1, i]$ 可以得出 $A[1, next_{j_0}] = A[i - next_{j_0} + 1, i]$，所以 $next_{j_0}$ 是 $next_i$ 的一个候选项。

再证 $next_{j_0}$ 是最大的。

使用反证法。假设存在一个 $j_1$ 为 $next_i$ 的候选项，且 $next_{j0} < j_1 < next_i$。

因为 $j_0$ 是 $next_i$ 的候选项，所以 $A[1, j_0] = A[i - j_0 + 1, i]$，同时取后 $j_1$ 个字符可以得到 $A[j_0 - j_1 + 1, j_0] = A[i - j_1 + 1, i]$。

因为 $j_1$ 为 $next_i$ 的候选项，所以 $A[i - j_1 + 1, i] = A[1, j_1]$，$A[j_0 - j_1 + 1, j_0] = A[i - j_1 + 1, i] = A[1, j_1]$，得到 $A[j_0 - j_1 + 1, j_0] = A[1, j_1]$。

此时，$j_1$ 也是一个 $next_{j_0}$ 的候选项，且比 $next_{j_0}$ 更大，与 $next_{j_0}$ 为最大候选项的定义不符，故假设不成立，证毕。

综上所述，$next_{i - 1}$ 如果被计算出来，$next_{i - 1}$ 的候选项分别为 $next_{i - 1}$，$next_{next_{i - 1}}$，$next_{next_{next_{i - 1}}} \dots$；

而可能成为 $next_i$ 的候选项的值分别为 $next_{i - 1} + 1$，$next_{next_{i - 1}} + 1$，$next_{next_{next_{i - 1}}} + 1 \dots$，因为 $A[1, j] = A[i - j + 1, i]$ 的前提条件是 $A[1, j - 1] = A[i - j + 1, i - 1]$。

所以，$next$ 可以这样求：

1. 初始化 $next_1 = 0$。

2. 维护一个变量 $j$ 从能选到最大的 $next_{i - 1}$ 往回遍历，直到 $j + 1$ 可以作为 $next_i$ 的候选项为止。（即 $A_{j + 1} = A_i$）

3. 如果连 $j = 0$ 都无法匹配，不存在 $next_i$，那么 $next_i = 0$。

由于定义的相似性，$f$ 可以直接用相同的方法求解。

初始时，$j$ 的值为 $0$；每次循环内，$j$ 的值最多会增加 $1$；$j$ 移动的总次数最多为 $2n + 2m$，时间复杂度为 $O(n + m)$。

代码

模板题代码：

#include <cstring>
#include <cstdio>

using namespace std;

int a, b, nxt[1000001];
char s1[1000001], s2[1000001];
int main(){
	scanf("%s%s", s1 + 1, s2 + 1);
	a = strlen(s1 + 1), b = strlen(s2 + 1);
	nxt[1] = 0;
	for (int i = 2, j = 0;i <= b;i ++){
		while (j && s2[j + 1] != s2[i]) j = nxt[j]; // 不断失配
		if (s2[j + 1] == s2[i]) j ++; // 匹配成功
		nxt[i] = j;
	} // 自我匹配
	for (int i = 1, j = 0;i <= a;i ++){
		while (j && s2[j + 1] != s1[i]) j = nxt[j];
		if (s2[j + 1] == s1[i]) j ++;
		if (j == b) printf("%d\n", i - b + 1), j = nxt[j]; // A 在 B 中出现
	}
	for (int i = 1;i <= b;i ++) printf("%d ", nxt[i]);
}