KMP 字符串匹配算法 | 学习笔记

$\rm KMP$ 字符串匹配

一些基本概念的解释：

• s 表示文本串(主串, 一般是较长的一个)

• p 表示模板串(子串, 在主串中匹配位置, 一般是较短的一个)

• $nxt$ 数组存储 字符串 $p$ 后缀与字符串 $p$ 前缀相等的情况（$\rm border$）中 长度最长情况 的长度

• $\rm border$ 见后文.

暴力解法 $ O(n^2)$

char s[N], p[M];
int ViolentMatch(char* s, char* p) {
	int sLen = strlen(s);
	int pLen = strlen(p);
 
	int i = 0, j = 0;
	while (i < sLen && j < pLen) {
		if (s[i] == p[j]) ++ i, ++ j;
			// 当前字符匹配成功（即S[i] == P[j]）
		else i = i - j + 1, j = 0;
			// 如果失配, 令i = i - (j - 1), j = 0 继续向后尝试匹配
	}
	// 匹配成功, 返回模式串p在文本串s中的位置, 否则返回-1
	if (j == pLen) return i - j;
	else return -1;
}

算法思路

考虑我们的暴力匹配过程. 对于每一个位置, 在匹配过程中, 对于：

模式串：abcabc
文本串：abcabdababcabc

在第六个位置失配之后, 下一个状态为：

模式串： abcabc
文本串：abcabdababcabc

然而在第一次匹配时我们已经得知了文本串位置 $1$（下标从 $0$ 开始）的信息, 在第二次匹配中又对它进行了重复匹配.

事实上, 我们希望能利用上一次匹配信息确定下一次匹配的开始位置, 从而跳过一些无效信息, 从位置 $3$ 开始匹配.

模式串：   abcabc
文本串：abcabdababcabc

如何保存以上信息呢？尝试把字符串抽象成线段理解.

尝试在 $S$ 上进行枚举, 对于扫描指针 $i$, 可以存下所有的可能为成功匹配的起点位置（图中按长度由短至长从上到下排列）, 即这些位置到 $i$ 的一段字符串为模式串 $P$ 的一个合法前缀, 下文中暂且称这样的串为 “前缀串”.

当扫描指针向右移动, 设当前位置的字符为 $c$, 直接更新当前维护的所出现的 $P$ 的前缀, 会出现四种情况：

1. 加入字符 $c$ 后该前缀串不是 $P$ 的前缀. -> 删除该串.
2. 加入字符 $c$ 后该前缀串仍是 $P$ 的前缀. -> 更新长度, 继续维护.
3. 加入字符 $c$ 后该前缀串仍是 $P$ 的前缀, 且长度等于 $P$. -> 匹配成功.
4. $c$ 与 $P$ 字符串的首字母相同. -> 另维护一个新的前缀串.

但暴力枚举维护这些串仍是 $O(n^2)$ 的时间复杂度, 尝试考虑当前维护的前缀串, 这些串是否具有一定关联？

不难发现, 较短的字符串同样是较长字符串的后缀（在 $S$ 中的位置相同）, 而较短字符串又是 $P$ 的一段前缀, 较长字符串中也必然包含这一段前缀. 因此较短字符串同时较长字符串的前缀和后缀, 当短字符串是长度小于等于长字符串的第一个字符串, 它就成为了该长字符串的最长前缀和后缀. 我们称一个字符串的最长字符串且满足同时为它的前缀和后缀的串为 $\rm border$.

形式化地, 定义字符串 $S$ 的 $\rm border$ 为最长字符串 $p$ (除其本身), 使得 $s[1, len_p] = s[len_s - len_p + 1, len_s]$.

注意到较长字符串是模式串 $P$ 的一个前缀, 因此很自然地, 我们想到要维护模式串 $P$ 的所有前缀 $\rm border$, 存储在 $nxt$ 数组中.

回到较短的前缀串是较长前缀串的 $\rm border$ 这件事, 因此我们可以直接通过较长串跳 $\rm border$ 的方式得到较短前缀串, 按上文提到的方式维护即可. 这也就是算法中 while (pos && s[i] != p[pos + 1]) pos = nxt[pos]; 循环跳 $\rm border$ 的精髓.

不难发现, 无论是较长前缀串, 亦或是较短前缀串, 它们都是模式串 $P$ 的一个 $\rm border$. 因此预处理模式串 $P$ 的所有位置的 $\rm border$ 并存储在 $nxt$ 数组中, 循环跳即可动态维护和匹配.

求子串的 $\rm next$ 数组

int pos = 0;
// 遍历 border 的指针
for (int i = 2; i <= n; i ++) {
// border 定义中除去了其本身, 因此 p_1 的 border 长度为 0, 直接从 p_2 开始计算. 
	while (pos and p[i] != p[pos + 1]) pos = nxt[pos];
	if (p[i] == p[pos + 1]) pos ++;
	nxt[i] = pos;
}

匹配过程

pos = 0;
for (int i = 1; i <= m; i ++) {
	while (pos and s[i] != p[pos + 1]) pos = nxt[pos];
	if (s[i] == p[pos + 1]) pos ++;
	if (pos == n) printf("%d ", i - n); // 匹配成功
}

至此, 相信你已经理解了被称为萌新杀手的 KMP 算法精髓.

时间复杂度分析

不难发现, 在 $\rm KMP$ 匹配过程中, 模式串与文本串下标指针都是单调不降的, 因此时间复杂度为 $O(n + m)$.

应用

求最短 border: OKR-Periods of Words

求不互相重叠的公共前后缀个数: [NOI2014] 动物园