基本数据结构 | 字符串

字符串

KMP 模式匹配

$\mathrm{KMP}$ 算法, 又称模式匹配算法, 能够在线性时间内判定字符串 $A[1 \sim N]$ 是否为字符串 $B[1 \sim M]$ 的子串, 并求出字符串 $A$ 在字符串 $B$ 中各次出现的位置。

首先, 一个 $\mathrm{O}(N M)$ 的朴素做法是, 尝试枚举字符串 $B$ 中的每个位置 $i$, 把字符串 $A$ 与字符串 $B$ 的后缀 $B[i \sim M]$ 对齐, 向后扫描逐一比较 $A[1]$ 与 $B[i], A[2]$ 与 $B[i+1] \cdots$ 是否相等。我们把这种比较过程称为 $A$ 与 $B$ 尝试进行 “匹配”。

其次, 这个问题使用字符串 Hash 也能在线性时间内求解。通过《Hash》一文中的 “兔子与兔子” 这道例题, 我们已经知道: 可以在 $O(N)$ 的时间内预处理一个字符串的所有前缀 Hash 值, 并在 $O(1)$ 的时间内查询该字符串任意一个子串的 Hash 值。所以, 一个很直接的想法是: 枚举字符串 $B$ 中的每个位置 $i(N \leq i \leq M)$, 检查字符串 $A$ 的 Hash 值与符串 $B$ 的子串 $B[i-N+1 \sim i]$ 的 Hash 值是否相同, 即可得到该问题的解。

KMP 算法能够更高效、更准确地处理这个问题, 并且能为我们提供一些额外的信息。详细地讲, KMP 算法分为两步:

1. 对字符串 $A$ 进行自我 “匹配”, 求出一个数组 $next$, 其中 $next[i]$ 表示 “ $A$ 中以 $i$ 结尾的非前缀子串” 与 “ $A$ 的前缀” 能够匹配的最长长度, 即:

$$\operatorname{next}[i]=\max \{j\}, \text { 其中 } j<i \text { 并且 } A[i-j+1 \sim i]=A[1 \sim j]$$

特别地, 当不存在这样的 $j$ 时, 令 $\operatorname{next}[i]=0$ 。
2. 对字符串 $A$ 与 $B$ 进行匹配, 求出一个数组 $f$, 其中 $f[i]$ 表示 “ $B$ 中以 $i$ 结尾的子串” 与 “ $A$ 的前缀” 能够匹配的最长长度, 即:

$$f[i]=\max \{j\}, \text{ 其中 } j \leq i \text{ 并且 } B[i-j+1 \sim i]=A[1 \sim j]$$

下面讨论 $next$ 数组的计算方法。根据定义, $n e x t[1]=0$ 。接下来我们按照 $i=2 \sim N$ 的顺序依次计算 $next[i]$ 。

假设 $next[1 \sim i-1]$ 已经计算完毕, 当计算 $next[i]$ 时, 根据定义, 我们需要找出所有满足 $j<i$ 且 $A[i-j+1 \sim i]=A[1 \sim j]$ 的整数, $j$ 并取最大值。为了敘述方便, 我们称满足这两个条件的 $j$ 为 $next[i]$ 的 “候选项”。

使用朴素算法计算 $next$ 数组

朴素的做法是枚举 $j \in[1, i-1]$, 并检查 $A[i-j+1 \sim i]$ 与 $A[1 \sim j]$ 是否相等。以下图中的字符串为例，当 $i=7$ 时，需要枚举下列 6 种情况：

$A[2 \sim 7]=$ “bababa”, 它与前缀 $A[1 \sim 6]=$ “ababab” 不相等。
$A[3 \sim 7]=$ “ababa”, 它与前缀 $A[1 \sim 5]=$ “ababa” 相等, 长度为 5 。
$A[4 \sim 7]=$ “baba”, 它与前缀 $A[1 \sim 4]=$ “abab” 不相等。
$A[5 \sim 7]=$ “aba”, 它与前缀 $A[1 \sim 3]=$ “aba” 相等, 长度为 3 。
$A[6 \sim 7]=$ “ba”, 它与前缀 $A[1 \sim 2]=$ “ab” 不相等。
$A[7 \sim 7]=$ “a”, 它与前缀 $A[1 \sim 1]=$ “a” 相等, 长度为 1 。

所以, 以 $i=7$ 结尾, 最多与 $A$ 的前缀匹配到 5 , $next[7]=5$ 。

该算法对每个 $i$ 枚举了 $i-1$ 个非前缀子串, 并检查与对应前缀的匹配情况, 时间复杂度不会低于 $O\left(N^{2}\right)$ 。能否更快地求出 $next$ 呢?

引理

若 $j_{0}$ 是 $\operatorname{next}[i]$ 的一个 “候选项”, 即 $j_{0}<i$ 且 $A\left[i-j_{0}+1 \sim i\right]=A\left[1 \sim j_{0}\right]$, 则小于 $j_{0}$ 的最大的 $n e x t[i]$ 的 “候选项” 是 $n e x t\left[j_{0}\right]$ 。换言之, $n e x t\left[j_{0}\right]+1 \sim j_{0}-1$ 之间的数都不是 $next[i]$ 的 “候选项”。

反证法证明：

假设存在 $n e x t\left[j_{0}\right]<j_{1}<j_{0}$ 使得 $j_{1}$ 为 $n e x t[i]$ 的 “候选项”, 即 $A[i-\left.j_{1}+1\right]=A\left[1 \sim j_{1}\right]$ 。如下图所示, 颜色相同的阴影部分代表相等的子串。

分别取 $A\left[i-j_{0}+1 \sim i\right]$ 和 $A\left[1 \sim j_{0}\right]$ 的后 $j_{1}$ 个字符, 显然也相等, 即 $A\left[i-j_{1}+\right. 1 \sim i]=A\left[j_{0}-j_{1}+1 \sim j_{0}\right]$ 从而 $A\left[j_{0}-j_{1}+1 \sim j_{0}\right]=A\left[1 \sim j_{1}\right]$, 与 $n e x t\left[j_{0}\right]$ “最大” 的性质矛盾。故假设不成立。

另一方面, $next\left[j_{0}\right]$ 显然是 $n e x t[i]$ 的“候选项”。

证毕。

使用优化的算法计算 $next$ 数组

根据引理, 当 $\operatorname{next}[i-1]$ 计算完毕时, 我们即可得知 $\operatorname{next}[i-1]$ 的所有 “候选项” 从大到小依次是 $\operatorname{next}[i-1]$, $\operatorname{next}[ next [i-1]]$, $\operatorname{next}[ next [ next [i-1]]] \cdots$ 而如果一个整数 $j$ 是 $next[i]$ 的 “候选项”, 那么 $j-1$ 显然也必须是 $next[i-1]$ 的 “候选项” (两个字符串 $A[i-j+1 \sim i]$ 和 $A[1 \sim j]$ 相等的前提是 $A[i-j+1 \sim i-1]$ 和 $A[1 \sim j-1]$ 相等)。因此, 在计算 $next[i]$ 时, 只需把 $\operatorname{next}[i-1]+1, next [ next [i- 1]]+1, \operatorname{next}[\operatorname{next}[\operatorname{next}[i-1]]]+1 \cdots$ 作为 $j$ 的选项即可。

仍然使用朴素算法中的例子。假设 $next[1 \sim 6]$ 已经被求出。按照定义, $\operatorname{next}[6]=$ 4, 即 $A[3 \sim 6]$ 与 $A[1 \sim 4]$ 匹配。

接下来 $A[7]=A[5]=\text{`a'}$, 在该字符上能够继续匹配, 由 $next[6]$ 匹配长度的最优性可知, 在字符 7 处继续匹配, $next[7] = 5$ 就是最优解。

我们继续考虑 $next [8]$。此时发现 $A[8]=\text{`a'}$ 与 $A[6]=\text{`a'}$ 二者不相等, 不能继续把匹配长度从 5 增长到 6 。我们只好把匹配长度缩短。由引理可知, 以 $i=7$ 为结尾的匹配长度除了 $j=next[7]=5$ 之外, 还有 $n e x t[5]=3$ 和 $next[3]=1$ 。我们依次尝试这两种稍短一些的匹配能否延伸到 $i=8$ 。

然而, $A[8]$ 与 $A[4], A[8]$ 与 $A[2]$ 都不相等, 无法延伸, 所以我们只能让 $i=8$ 从 $A$ 字符串开头重新开始匹配, $A[8]=A[1]$, 匹配长度为 1 , $next[8]=1$ 。

在讨论优化后的算法的时间复杂度之前, 我们先写出算法实现的框架和代码。

KMP 算法 $next$ 数组的求法

1. 初始化 $next[1]=j=0$, 假设 $next[1 \sim i-1]$ 已求出, 下面求解 $\operatorname{next}[i]$ 。
2. 不断尝试扩展匹配长度 $j$, 如果扩展失败 (下一个字符不相等), 令 $j$ 变为 $n e x t[j]$, 直至 $j$ 为 0 (应该重新从头开始匹配)。
3. 如果能够扩展成功, 匹配长度 $j$ 就增加 1 。$next[i]$ 的值就是 $j$ 。

ne[0] = ne[1] = 0;
for (int i = 2, j = 0; i <= n; ++i) {
	while (j && a[i] != a[j + 1]) j = ne[j];
	if (a[i] == a[j + 1]) ++j;
	ne[i] = j;
}

KMP 算法 $f$ 数组的求法

因为定义的相似性, 求解 $f$ 与求解 $next$ 的过程是基本一致的。

for (int i = 1, j = 0; i <= m; ++i) {
	while (j && b[i] != a[j + 1]) j = ne[j];
	if (b[i] == a[j + 1]) ++j;
	f[i] = j;
	if (f[i] == n) { // 此时就是 A 在 B 中的某一次出现
		j = ne[j]; // 进行下一轮匹配
		// 匹配成功后的逻辑
	}
}

这就是 KMP 模式匹配算法。在上面代码的 while 循环中, $j$ 的值不断减小, $j=$ $n e x t[j]$ 的执行次数不会超过每层 for 循环开始时 $j$ 的值与 while 循环结束时 $j$ 的值之差。而在每层 for 循环中, $j$ 的值至多增加 1 。因为 $j$ 始终非负, 所以在整个计算过程中, $j$ 减小的幅度总和不会超过 $j$ 增加的幅度总和。故 $j$ 的总变化次数至多为 $2(N+M)$ 。整个算法的时间复杂度为 $O(N+M)$ 。

---

141. 周期

一个字符串的前缀是从第一个字符开始的连续若干个字符，例如 abaab 共有 $5$ 个前缀，分别是 a，ab，aba，abaa，abaab。

我们希望知道一个 $N$ 位字符串 $S$ 的前缀是否具有循环节。

换言之，对于每一个从头开始的长度为 $i$（$i>1$）的前缀，是否由重复出现的子串 $A$ 组成，即 $AAA…A$ （$A$ 重复出现 $K$ 次,$K>1$）。

如果存在，请找出最短的循环节对应的 $K$ 值（也就是这个前缀串的所有可能重复节中，最大的 $K$ 值）。

输入格式

输入包括多组测试数据，每组测试数据包括两行。

第一行输入字符串 $S$ 的长度 $N$。

第二行输入字符串 $S$。

输入数据以只包括一个 $0$ 的行作为结尾。

输出格式

对于每组测试数据，第一行输出 Test case # 和测试数据的编号。

接下来的每一行，输出具有循环节的前缀的长度 $i$ 和其对应 $K$，中间用一个空格隔开。

前缀长度需要升序排列。

在每组测试数据的最后输出一个空行。

数据范围

$2 \le N \le 1000000$

输入样例：

3
aaa
4
abcd
12
aabaabaabaab
0 

输出样例：

Test case #1
2 2
3 3

Test case #2

Test case #3
2 2
6 2
9 3
12 4 

算法分析

对字符串 $S$ 自匹配求出 $next$ 数组, 根据定义, 对于每个 $i, S[i-next[i]+1 \sim i]$ 与 $S[1 \sim n e x t[i]]$ 是相等的, 并且不存在更大的 $next$ 值满足这个条件。

引理：

$S[1 \sim i]$ 具有长度为 $l e n<i$ 的循环元的充要条件是 $len$ 能整除 $i$ 并且 $S[len+ 1\sim i]=S[1 \sim i-l e n]$ (即 $i-l e n$ 是 $n e x t[i]$ 的 “候选项”, 在讲解 KMP 算法时我们提到了 “候选项” 的含义)。

证明：

先证必要性。设 $S[1 \sim i]$ 具有长度为 $len$ 的循环元, 显然 $len$ 能整除 $i$, 并且 $S[1 \sim i-l e n]$ 和 $S[l e n+1 \sim i]$ 都是由 $i / l e n-1$ 个循环元构成的。故 $S[1 \sim i- len ]=S[ len +1 \sim i]$ 。

再证充分性。设 $len$ 能整除 $i$ 并且 $S[ len +1 \sim i]=S[1 \sim i- len ]$ 。因为 $len < i$, 所以 $S[1 \sim i-len ]$ 和 $S[len +1 \sim i]$ 的长度不小于 $len$ 且是 $len$ 的倍数。二者各取前 $len$ 个字符, 有 $S[1 \sim l e n]=S[l e n+1 \sim 2 * l e n]$ 。依此类推, 不断向后取 $len$ 个 字符, 可以发现 $S[1 \sim i-l e n]$ 和 $S[l e n+1 \sim i]$ 是以 $len$ 为间隔错位对齐的, 如下图所示。故 $S[1 \sim l e n]$ 是 $S$ 的循环元。

证毕。

根据引理, 当 $i-n e x t[i]$ 能整除 $i$ 时, $S[1 \sim i-n e x t[i]]$ 就是 $S[1 \sim i]$ 的最小循环元。它的最大循环次数就是 $i /(i-next[i])$ 。其中 $i-next[i]$ 能整除 $i$ 的条件是为了保证循环元每次重复的完整性。例如上图中 $i=7$ 时, 最小循环元 “ab” 的第 4 次重复就尚未完成。

进一步地, 如果 $i-next[ next [i]]$ 能整除 $i$, 那么 $S[1 \sim i-next[next[i]]]$ 就是 $S[1 \sim i]$ 的次小循环元。依此类推, 我们还可以找出 $S[1 \sim i]$ 所有可能的循环元。

值得指出的一个性质是, 一个字符串的任意循环元的长度必然是最小循环元长度的倍数。

Solution

---

最小表示法

给定一个字符串 $S[1 \sim n]$, 如果我们不断把它的最后一个字符放到开头, 最终会得到 $n$ 个字符串, 称这 $n$ 个字符串是循环同构的。这些字符串中字典序最小的一个, 称为字符串 $S$ 的最小表示。

例如 $S=$ “abca”, 那么它的 4 个循环同构字符串为 “abca”, “aabc”, “caab”, “bcaa”, $S$ 的最小表示为 “aabc”。与 $S$ 循环同构的字符串可以用该字符串在 $S$ 中的起始下标表示, 因此我们用 $B[i]$ 来表示从 $i$ 开始的循环同构字符串, 即 $S[i \sim n]+S[1 \sim i-1]$ 。

如何求出一个字符串的最小表示? 最朴素的方法是：按照定义, 依次比较这 $n$ 个循环同构的字符串, 找到其中字典序最小的一个。比较两个循环同构字符串 $B[i]$ 与 $B[j]$ 时, 我们也采用直接向后扫描的方式, 依次取 $k=0,1,2, \cdots$, 比较 $B[i+k]$ 与 $B[j+k]$ 是否相等, 直至找到一个不相等的位置, 从而确定 $B[i]$ 与 $B[j]$ 的大小关系。

实际上,一个字符串的最小表示可以在 $O(n)$ 的线性时间内求出。我们首先把 $S$ 复制一份接在它的结尾, 得到的字符串记为 $S S$ 。显然, $B[i]=S S[i \sim i+n-1]$ 。

对于任意的 $i, j$, 我们仔细观察 $B[i]$ 与 $B[j]$ 的比较过程:

如果在 $i+k$ 与 $j+k$ 处发现不相等, 假设 $S S[i+k]>S S[j+k]$, 那么我们当然可以得知 $B[i]$ 不是 $S$ 的最小表示(因为存在一个更小的循环同构串 $B[j]$ )。除此之外, 我们还可以得知 $B[i+1], B[i+2], \cdots, B[i+k]$ 也都不是 $S$ 的最小表示。这是因为对于 $1 \leq p \leq k$, 存在一个比 $B[i+p]$ 更小的循环同构串 $B[j+p]$ (从 $i+p$ 与 $j+p$ 开始向后扫描, 同样会在 $p=k$ 时发现不相等, 并且 $S S[i+k]>S S[j+k]$ ）。

同理, 如果 $S S[i+k]<S S[j+k]$, 那么 $B[j], B[j+1], \cdots, B[j+k]$ 都不是 $S$ 的最 小表示, 直接跳过这些位置, 一定不会遗漏最小表示。

最小表示法算法流程：

1. 初始化 $i=1, j=2$ 。
2. 通过直接向后扫描的方法, 比较 $B[i]$ 与 $B[j]$ 两个循环同构串。
   (1) 如果扫描了 $n$ 个字符后仍然相等, 说明 $S$ 有更小的循环元 (例如 catcat 有循环元 cat), 并且该循环元已扫描完成, $B[\min (i, j)]$ 即为最小表示, 算法结束。
   (2) 如果在 $i+k$ 与 $j+k$ 处发现不相等:
   若 $S S[i+k]>S S[j+k]$, 令 $i=i+k+1$ 。若此时 $i=j$, 再令 $i=i+1$ 。
   若 $S S[i+k]<S S[j+k]$, 令 $j=j+k+1$ 。若此时 $i=j$, 再令 $j=j+1$ 。
3. 若 $i>n$ 或 $j>n$, 则 $B[\min (i, j)]$ 为最小表示; 否则重复第 2 步。

该算法通过两个指针不断向后移动的形式, 尝试比较每两个循环同构串的大小。利用上面的性质, 及时排除掉不可能的选项。当其中一个移动到结尾时, 就考虑过了所有可能的二元组 $(B[i], B[j])$, 从而得到了最小表示。

如果每次比较向后扫描了 $k$ 的长度, 则 $i$ 或 $j$ 二者之一会向后移动 $k$, 而 $i$ 和 $j$ 合计一共最多向后移动 $2 n$ 的长度, 因此该算法的复杂度为 $\mathrm{O}(n)$ 。

// 最小表示法
int n = strlen(s + 1);
for (int i = 1; i <= n; i++) s[n+i] = s[i];
int i = 1, j = 2, k;
while (i <= n && j <= n) {
	for (k = 0; k < n && s[i+k] == s[j+k]; k++);
	if (k == n) break; // s likes "aaaaa"
	if (s[i+k] > s[j+k]) {
		i = i + k + 1;
		if (i == j) i++;
	} else {
		j = j + k + 1;
		if (i == j) j++;
	}
}
ans = min(i, j);