「学习笔记」KMP 算法-五八三

由于新文章的做法与旧文章不同, 因此 KMP 算法仍保留旧文章, 且经过模板题测验, 新的做法明显慢于旧的做法, 但是, 新做法更好理解.

前置知识#

前缀是指从串首开始到某个位置 $i$ 结束的一个特殊子串.

真前缀 指除了 $S$ 本身的 $S$ 的前缀.

举例来说, 字符串 abcabeda 的所有前缀为 {a, ab, abc, abca, abcab, abcabe, abcabed, abcabeda}, 而它的真前缀为 {a, ab, abc, abca, abcab, abcabe, abcabed}.

后缀是指从某个位置 $i$ 开始到整个串末尾结束的一个特殊子串.

真后缀 指除了 $S$ 本身的 $S$ 的后缀.

举例来说, 字符串 abcabeda 的所有后缀为 {a, da, eda, beda, abeda, cabeda, bcabeda, abcabeda}, 而它的真后缀为 {a, da, eda, beda, abeda, cabeda, bcabeda}.

前缀函数#

定义: 给定一个长度为 $n$ 的字符串 $s$ , 其前缀函数被定义为一个长度为 $n$ 的数组 nxt. 其中 nxt[i] 是子串 s[0 ~ i] 最长的相等的真前缀和真后缀的长度.

用数学语言描述如下:

n x t [i] = max_{k = 0 \sim i} {s [0 \sim k - 1] = s [i - (k - 1) \sim i]}

$nxt \left [i \right ] = \max_{k = 0 \sim i} \{s \left[0 \sim k - 1 \right ] = s \left[i - \left(k - 1 \right) \sim i \right]\}$

特别地, nxt[0] = 0, 因为不存在真前缀和真后缀.

过程#

举例来说, 对于字符串 aabaaab,

nxt[0] = 0, a 没有真前缀和真后缀.

nxt[1] = 1, aa 只有一对相等的真前缀和真后缀: a, 长度为 $1$ .

nxt[2] = 0, aab 没有相等的真前缀和真后缀.

nxt[3] = 1, aaba 只有一对相等的真前缀和真后缀: a, 长度为 $1$ .

nxt[4] = 2, aabaa 相等的真前缀和真后缀有 a, aa, 最长的长度为 $2$ .

nxt[5] = 2, aabaaa 相等的真前缀和真后缀有 a, aa, 最长的长度为 $2$ .

nxt[6] = 3, aabaaab 相等的真前缀和真后缀只有 aab, 最长的长度为 $3$ .

暴力求法#

cin >> s1;
len1 = s1.length();
for (int i = 1; i < len1; ++ i) {
	for (int j = i; j; -- j) {
    	if (s1.substr(0, j) == s1.substr(i - (j - 1), j)) {
			nxt[i] = j;
			break ;
		}
	}
}

优化#

第一个重要的观察是 相邻的前缀函数值至多增加 $1$ .

参照下图所示, 只需如此考虑: 当取一个尽可能大的 nxt[i + 1] 时, 必然要求新增的 s[i + 1] 也与之对应的字符匹配, 即 s[i + 1] = s[nxt[i]], 此时 s[i + 1] = s[i] + 1.

\underset{n x t [i + 1] = 4}{\underset{⏟}{\overset{n x t [i] = 3}{\overset{⏞}{s_{0} s_{1} s_{2}}} s_{3}}} \dots \underset{n x t [i + 1] = 4}{\underset{⏟}{\overset{n x t [i] = 3}{\overset{⏞}{s_{i - 2} s_{i - 1} s_{i}}} s_{i + 1}}}

$\underbrace{\overbrace{s_0 ~ s_1 ~ s_2}^{nxt[i] = 3} ~ s_3}_{nxt[i+1] = 4} ~ \dots ~ \underbrace{\overbrace{s_{i-2} ~ s_{i-1} ~ s_{i}}^{nxt[i] = 3} ~ s_{i+1}}_{nxt[i+1] = 4}$

所以当移动到下一个位置时, 前缀函数的值要么增加一, 要么维持不变, 要么减少.

当 s[i+1] != s[nxt[i]] 时, 我们希望找到对于子串 s[0 ~ i], 仅次于 nxt[i] 的第二长度 $j$ , 使得在位置 $i$ 的前缀性质仍得以保持, 也即 s[0 ~ (j - 1)] = s[(i - j + 1) ~ i]：

\overset{n x t [i]}{\overset{⏞}{\underset{j}{\underset{⏟}{s_{0} s_{1}}} s_{2} s_{3}}} \dots \overset{n x t [i]}{\overset{⏞}{s_{i - 3} s_{i - 2} \underset{j}{\underset{⏟}{s_{i - 1} s_{i}}}}} s_{i + 1}

$\overbrace{\underbrace{s_0 ~ s_1}_j ~ s_2 ~ s_3}^{nxt[i]} ~ \dots ~ \overbrace{s_{i-3} ~ s_{i-2} ~ \underbrace{s_{i-1} ~ s_{i}}_j}^{nxt[i]} ~ s_{i+1}$

如果我们找到了这样的长度 $j$ , 那么仅需要再次比较 s[i + 1] 和 s[j]. 如果它们相等, 那么就有 nxt[i + 1] = j + 1. 否则, 我们需要找到子串 s[0 ~ i] 仅次于 $j$ 的第二长度 $j_{2}$ , 使得前缀性质得以保持, 如此反复, 直到 $j = 0$ . 如果 s[i + 1] != s[0], 则 nxt[i + 1] = 0.

观察上图可以发现, 因为 s[0 ~ nxt[i] - 1] = s[i - nxt[i] + 1 ~ i], 所以对于 s[0 ~ i] 的第二长度 $j$ , 有这样的性质:

\overset{n x t [i]}{\overset{⏞}{\underset{j}{\underset{⏟}{s_{0} s_{1}}} s_{2} \underset{j}{\underset{⏟}{s_{3} s_{4}}}}} \dots \overset{n x t [i]}{\overset{⏞}{s_{i - 4} s_{i - 3} s_{i - 2} \underset{j}{\underset{⏟}{s_{i - 1} s_{i}}}}} s_{i + 1}

$\overbrace{\underbrace{s_0 ~ s_1}_j ~ s_2 ~ \underbrace{s_3 ~ s_4}_j}^{nxt[i]} ~ \dots ~ \overbrace{s_{i-4} ~ s_{i-3} ~ s_{i-2} ~ \underbrace{s_{i-1} ~ s_{i}}_j}^{nxt[i]} ~ s_{i+1}$

s[0 ~ j - 1] = s[i - j + 1 ~ i]= s[nxt[i] - j ~ nxt[i] - 1]
也就是说 $j$ 等价于子串 s[nxt[i] - 1] 的前缀函数值 (你可以把上面的 $i$ 换成 nxt[i] - 1), 即 j = nxt[nxt[i] - 1]. 同理, 次于 $j$ 的第二长度等价于 s[j - 1] 的前缀函数值.

cin >> s1;
len1 = s1.length();
for (int i = 1; i < len1; ++ i) {
    int j = nxt[i - 1];
	while (j && s1[i] != s1[j]) {
		j = nxt[j - 1];
	}
	if (s1[i] == s1[j]) {
		++ j;
	}
	nxt[i] = j;
}

KMP 算法#

给定一个文本 $t$ 和一个字符串 $s$ , 我们尝试找到并展示 $s$ 在 $t$ 中的所有出现.

为了简便起见, 我们用 $n$ 表示字符串 $s$ 的长度, 用 $m$ 表示文本 $t$ 的长度.

我们构造一个字符串 $s$ + # + $t$ , 其中 # 为一个既不出现在 $s$ 中也不出现在 $t$ 中的分隔符.

接下来计算该字符串的前缀函数. 现在考虑该前缀函数除去最开始 $n + 1$ 个值 (即属于字符串 $s$ 和分隔符的函数值) 后其余函数值的意义. 根据定义，nxt[i] 为右端点在 $i$ 且同时为一个前缀的最长真子串的长度, 具体到我们的这种情况下, 其值为与 $s$ 的前缀相同且右端点位于 $i$ 的最长子串的长度. 由于分隔符的存在, 该长度不可能超过 $n$ . 而如果等式 nxt[i] = n 成立, 则意味着 $s$ 完整出现在该位置 (即其右端点位于位置 $i$ ). 注意该位置的下标是对字符串 $s$ + # + $t$ 而言的.

因此如果在某一位置 $i$ 有 nxt[i] = n 成立, 则字符串 $s$ 在字符串 $t$ 的 $i - (n - 1) - (n + 1) = i - 2n$ 处出现.

正如在前缀函数的计算中已经提到的那样, 如果我们知道前缀函数的值永远不超过一特定值, 那么我们不需要存储整个字符串以及整个前缀函数, 而只需要二者开头的一部分. 在我们这种情况下这意味着只需要存储字符串 $s$ + # 以及相应的前缀函数值即可. 我们可以一次读入字符串 $t$ 的一个字符并计算当前位置的前缀函数值.

因此 Knuth–Morris–Pratt 算法（简称 KMP 算法）用 $O_{n + m}$ 的时间以及 $O_{n}$ 的内存解决了该问题.

/*
  The code was written by yifan, and yifan is neutral!!!
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>
inline T read() {
	T x = 0;
	bool fg = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		fg |= (ch == '-');
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return fg ? ~x + 1 : x;
}

const int N = 1e6 + 5;

int nxt[N << 1];
char s1[N], s2[N], cur[N << 1];

inline void get_nxt(char* s) {
	int len = strlen(s);
	for (int i = 1; i < len; ++ i) {
		int j = nxt[i - 1];
		while (j && s[i] != s[j]) {
			j = nxt[j - 1];
		}
		if (s[i] == s[j]) {
			++ j;
		}
		nxt[i] = j;
	}
}

int main() {
	cin >> s1 >> s2;
	scanf("%s%s", s1, s2);
	strcpy(cur, s2);
	strcat(cur, "#");
	strcat(cur, s1);
	get_nxt(cur);
	int l1 = strlen(s1), l2 = strlen(s2);
	for (int i = l2 + 1; i <= l1 + l2; ++ i) {
		if (nxt[i] == l2) {
			cout << i - 2 * l2 + 1 << '\n';
		}
	}
	for (int i = 0; i < l2; ++ i) {
		cout << nxt[i] << ' ';
	}
	return 0;
}

文章版权归作者所有，未经允许请勿转载，侵权请联系 admin@trc20.tw 删除。

THE END

博客文章