0x15字符串

KMP模式匹配

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

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

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

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

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

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

以 $i = 7$ 为结尾的“非前缀子串”有6个，分别是 $A[2\sim 7], A[3\sim 7], \dots, A[7\sim 7]$ ，如下图所示（因为 $A[1\sim 7]$ 是前缀，所以不算在内）。如果使用朴素算法求 next[7]，那么根据 next 的定义，我们可以枚举下列几种情况：

$A[2\sim 7] = "\mathrm{bababa}"$ ，它与前缀 $A[1\sim 6] = "\mathrm{ababab}"$ 不匹配。

$A[3\sim 7] = "\mathrm{ababa}"$ ，它与前缀 $A[1\sim 5] = \text{"ababa"}$ 匹配，长度为5。

$A[4\sim 7] = \text{"baba"}$ ，它与前缀 $A[1\sim 4] = \text{"abab"}$ 不匹配。

$A[5\sim 7] = \text{"aba"}$ ，它与前缀 $A[1\sim 3] = \text{"aba"}$ 匹配，长度为3。

$A[6\sim 7] = "ba"$ ，它与前缀 $A[1\sim 2] = "ab"$ 不匹配。

$A[7\sim 7] = \text{"a"}$ ，它与前缀 $A[1\sim 1] = \text{"a"}$ 匹配，长度为1。

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

能否更快地求出 next 呢？我们不妨假设 $\text{next}[1 \sim 6]$ 已经被求出。按照上述定义， $\text{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{"b"}$ 二者不相等，不能继续把匹配长度从5增长到6。我们只好把匹配长度缩短。以 $i = 7$ 为结尾的匹配长度除了 $j = 5$ 之外， $A[5\sim 7]$ 与 $A[1\sim 3]$ 还能进行长度为3的匹配， $A[7\sim 7]$ 与 $A[1\sim 1]$ 还能进行长度为1的匹配。我们依次尝试这两种稍短一些的匹配能否延伸到 $i = 8$ 。

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

那么我们是如何得知要考虑5,3,1这些匹配长度的呢？首先， $next[7] = 5$ ，这说

明从7往前的5个字符与 $A[1\sim 5]$ 是相等的。如果存在一个新的 $j$ ，使得从5往前的 $j$ 个字符与 $A[1\sim j]$ 是相等的，那么从7往前的 $j$ 个字符与 $A[1\sim j]$ 也是相等的。这样的 $j$ 最大是多少呢？当然就是以5为结尾能匹配的最长前缀长度，即next[5]！

同理，在考虑完 $j = \text{next}[5] = 3$ 之后，下一个要考虑的匹配长度就是 next[3]。依此类推，我们得到了以下算法：

KMP算法 next数组的求法

1. 初始化 $next[1] = j = 0$ ，假设 $next[1 \sim i - 1]$ 已求出，下面求解 $next[i]$ 。

2. 不断尝试扩展匹配长度 $j$ ，如果扩展失败（下一个字符不相等），令 $j$ 变为 next[j]，直至 $j$ 为 0（应该重新从头开始匹配）。

3. 如果能够扩展成功，匹配长度 $j$ 就增加 1。next[i] 的值就是 $j$ 。

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

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

KMP算法  $f$  数组的求法  
for（int  $\mathrm{i} = 1$  ，  $\mathrm{j} = 0$  ；i<=m；i++){while  $(j > 0\& \& (j == n||b[i] != a[j + 1]))j = next[j];$  if  $(\mathtt{b}[i] == \mathtt{a}[j + 1])j + + ;$  （20 $f[i] = j;$  //if  $(f[i] == n)$  ，此时就是  $A$  在  $B$  中的某一次出现

这就是KMP模式匹配算法，其时间复杂度为 $O(N + M)$ ，这里我们就不再证明了。

【例题】Period POJ1961

如果一个字符串 $S$ 是由一个字符串 $T$ 重复 $K$ 次形成的，则称 $T$ 是 $S$ 的循环元。使 $K$ 最大的字符串 $T$ 称为 $S$ 的最小循环元，此时的 $K$ 称为最大循环次数。

现在给定一个长度为 $N$ 的字符串 $S$ ，对 $S$ 的每一个前缀 $S[1 \sim i]$ ，如果它的最大循环次数大于 1，则输出该前缀的最小循环元长度和最大循环次数。

对字符串 $S$ 自匹配求出 next 数组, 根据定义, 对于每个 $i$ , $S[i - next[i] + 1 \sim i]$

与 $S[1 \sim next[i]]$ 是相等的，并且不存在更大的 next 值满足这个条件。

如上图所示，仔细分析 next 数组的含义与计算过程，可以发现：当 $i - \text{next}[i]$ 能整除 $i$ 时， $S[1 \sim i - \text{next}[i]]$ 就是 $S[1 \sim i]$ 的最小循环元。它的最大循环次数就是 $i / (i - \text{next}[i])$ 。

在上面这个结论中， $i - next[i]$ 能整除 $i$ 的条件是为了保证循环元每次重复的完整性。例如上图中 $i = 7$ 时，最小循环元"ab"的第4次重复就尚未完成。

进一步地，如果 $i - next \left[ next[i] \right]$ 能整除 $i$ ，那么 $S[1 \sim i - next[next[i]]]$ 就是 $S[1 \sim i]$ 的次小循环元。依此类推，我们还可以找出 $S[1 \sim i]$ 所有可能的循环元（注意判断是否能整除以保证完整性）。

i a b a b a b a b 12345678 next[8] = 6 a b a b a b a b 12345678 next[6] = 4  $\Rightarrow S[1\sim 4] = S[3\sim 6] = S[5\sim 8]$  a b a b a b a b 12345678 next[4] = 2 a b a b a b a b 12345678 next[2] = 0 char a[1000010]; int next[1000010], n, T; void calc_next() { next[1] = 0; for (int i = 2, j = 0; i <= n; i++) { while (j > 0 && a[i] != a[j+1]) j = next[j]; if (a[i] == a[j+1]) j++; next[i] = j; } } int main() { while (cin >> n && n) { scanf("%s", a + 1); calc_next(); printf("Test case %d\n", ++T);

for (int i = 2; i <= n; i++) { if (i % (i - next[i]) == 0 && i / (i - next[i]) > 1) printf("%d%d\n", i, i / (i - next[i])); } puts(""); }

最小表示法

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

例如 $S = \text{"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,\dots$ ，比较 $B[i + k]$ 与 $B[j + k]$ 是否相等，直至找到一个不相等的位置，从而确定 $B[i]$ 与 $B[j]$ 的大小关系。

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

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

$S =$  "bacacabc",  $i = 2,j = 4,k = 3$  i+k baca|cabcbacacabc baca|bcbacacabc jj+K

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

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

根据这个性质，我们可以用这样的算法来求最小表示：

最小表示法

1. 初始化 $i = 1, j = 2$ 。

2. 通过直接向后扫描的方法，比较 $B[i]$ 与 $B[j]$ 两个循环同构串。

(1) 如果扫描了 $n$ 个字符后仍然相等，说明 $S$ 只由 1 种字符构成，任意 $B[i]$ 都是它的最小表示。
(2) 如果在 $i + k$ 与 $j + k$ 处发现不相等：

若 $SS[i + k] > SS[j + k]$ ，令 $i = i + k + 1$ 。若此时 $i = j$ ，再令 $i = i + 1$ 。

若 $SS[i + k] < SS[j + k]$ ，令 $j = j + k + 1$ 。若此时 $i = j$ ，再令 $j = j + 1$ 。

1. 若 $i > n$ ， $B[j]$ 为最小表示；若 $j > n$ ， $B[i]$ 为最小表示；否则重复第2步。

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

如果每次比较向后扫描了 $k$ 的长度，则 $i$ 或 $j$ 二者之一会向后移动 $k$ ，而 $i$ 和 $j$ 合计一共最多向后移动 $2n$ 的长度，因此该算法的复杂度为 $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只由一个字符构成，形如"aaaa"  
    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); // B[ans]是最小表示