【KMP算法】周期

题目

141. 周期 - AcWing题库

---

一个字符串的前缀是从第一个字符开始的连续若干个字符，例如 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

解题

方法一：KMP算法

思路

KMP算法及其原理在此不做说明，详见：KMP算法。

以下思路来自：y总的视频讲解。

设有一段字符串 $s[1\dots n]$ ，那么通过KMP算法构造出的 $nexts$ 数组中 $nexts[n]$ 为 $s[1 \dots n]$ 的最长相等前后缀，把 $s[1 \dots n]$ 复制一份并向后平移使得两串最长相等前后缀重合，如图：

由于 $s'$ 是由 $s$ 平移来的，所以有 $s[1 \dots n - nexts[n]] = s'[1 \dots n - nexts[n]]$ （以下称 $n - nexts[n]$ 为 $T$）：

又由于前后缀 $s[T \dots n]$ 与 $s'[1 \dots nexts[n]]$ 相等，故有 $s'[1 \dots T] = s[T \dots 2T]$ ：

再由于 $s'$ 是由 $s$ 平移来的，所以 $s[T \dots 2T] = s'[T \dots 2T]$ ：

由于前后缀 $s[T \dots n]$ 与 $s'[1 \dots nexts[n]]$ 相等，所以 $s[2T \dots n] = s'[T \dots nexts[n]]$ （图中 $PT$）：

图中可以很明显的在 $s'$ 中看出 $PT$ 是 $T$ 的一个前缀，而 $T$ 是 $s[1 \dots n]$ 的一个循环节^[1]（$T = n - nexts[n]$）。

证明 $T$ 是最小的一个循环节？

反证法：假设有 $T'$ 是一个更小的循环节（$T' < T$），我们像刚才那样对齐，只不过对齐的是循环节 $T'$ ：

如图 $s[T' \dots n] = s[1 \dots 2T' + PT']$ ，这段相同的前后缀是由两个完成循环节 $T'$ 和一个循环节前缀 $PT'$ 构成的，所以我们就找到了一对长度为 $n - T'$ 的相等前后缀，又因为 $T' < T$ ，所以 $n - T' > n - T \Longrightarrow n - T' > nexts[n]$ 。但是在KMP算法构造出的 $nexts$ 数组中，$nexts[n]$ 表示的是所有的相等前后缀中长度最长的，现在却出现了更长的相等前后缀，所以 $T'$ 的存在会造成矛盾，故 $T' < T$ 不存在，也就是说 $T$ 一定是最小循环节。

如果 $T \mid n$ ^[2]，根据题目要求（最小循环节，且长度能整除字符串长度）， $T$ 就是答案。

但如果 $T \nmid n$ 呢？是否存在一个稍微大一点的循环节 $T' (T' > T)$ 使得 $T' \mid n$ 呢？

如何证明当 $T \nmid n (T是最小循环节的长度)$ 时，不存在任何循环节 $T'$ 使得 $T' \mid n$ ？

• 证明性质：如果存在 $T'>T$ ，则 $T'$ 一定是 $T$ 的倍数（$T \mid T'$）：

• 反证法：假设 $\exist T'(T' > T 且 T \nmid T')$ ^[3] ，设 $d = \gcd(T, T')$ 。$\because T \nmid T \,\, \therefore d \ne T \,\,\,\, 又\because d \mid T \,\, \therefore d < T$ 。此时如果能证明 $d$ 也是一个循环节，那么就存在矛盾（存在更小的循环节比 $T$ 小），就能反证不能存在这样的 $T'$ 。

  • 证明 $d$ 也是一个循环节就是要证明 $\forall{i}, s_i = s_{i + d}$ ^[4] ：

  • 根据裴蜀定理，$d = xT - yT'$ ，那么（这段建议去看y总的视频讲解）:

    $$\forall{i}, s_{i} = s_{i + T} = s_{i + 2T} = \dots = s_{i + xT} = s_{i + xT - T'} = s_{i + xT - 2T'} = \dots = s_{i + xT - yT'} = s_{i + d}$$

  • $d$ 是一个循环节得证。

• 此时就找到了一个更小的循环节 $d (d < T)$ ，与 $T$ 存在矛盾，所以不存在 $T'(T' > T 且 T \nmid T')$ 。

所以 $T'$ 必然是 $T$ 的倍数，也就是说所有循环节长度都是最小循环节长度的倍数，当 $T \nmid n$ 时，$T$ 的所有倍数 $T'$ 就更不能整除 $n$ 了，也就是说：只要最小循环节不能整除 $n$ ，那么所有的循环节都不能整除 $n$ ，就一定无解。

注意：Java一个case一个case输出会TLE，用 StringBuilder 拼接完后一起输出。

参考：AcWing 141. 周期（蓝桥杯集训·每日一题） - yxc

代码

字符串下标从 $1$ 开始的写法（与思路相同）：

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int cnt = 0;
        StringBuilder ans = new StringBuilder();
        while (true) {
            int n = Integer.parseInt(in.readLine());
            if (n == 0) break;
            char[] s = ('\0' + in.readLine()).toCharArray();
            int[] nexts = new int[n + 1];
            for (int i = 2, j = 0; i <= n; ++i) {
                while (j > 0 && s[i] != s[j + 1]) j = nexts[j];
                if (s[i] == s[j + 1]) ++j;
                nexts[i] = j;
            }
            ans.append("Test case #").append(++cnt).append('\n');
            for (int i = 2; i <= n; ++i) {
                int p = i - nexts[i];
                if (i % p == 0 && i / p > 1) ans.append(i).append(' ').append(i / p).append('\n');
            }
            ans.append('\n');
        }
        System.out.print(ans);
    }
}

字符串下标从 $0$ 开始的写法（处理稍微麻烦一点）：

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int cnt = 0;
        StringBuilder ans = new StringBuilder();
        while (true) {
            int n = Integer.parseInt(in.readLine());
            if (n == 0) break;
            char[] s = in.readLine().toCharArray();
            int[] nexts = new int[n];
            nexts[0] = -1;
            for (int i = 1, j = -1; i < n; ++i) {
                while (j >= 0 && s[i] != s[j + 1]) j = nexts[j];
                if (s[i] == s[j + 1]) ++j;
                nexts[i] = j;
            }
            ans.append("Test case #").append(++cnt).append('\n');
            for (int i = 1; i < n; ++i) {
                int len = i + 1, p = i - nexts[i];
                if (len % p == 0 && len / p > 1) ans.append(len).append(' ').append(len / p).append('\n');
            }
            ans.append('\n');
        }
        System.out.print(ans);
    }
}

---

1. 这里的循环节定义与题目中不同，这里提到的循环节，整个字符串的长度可以不被其长度整除。 ↩︎

2. $\mid$ 是整除符号， $a \mid b$ 表示：$b$ 能被 $a$ 整除（或 $a$ 整除 $b$），类似地， $\nmid$ 为不能整除符号。 ↩︎

3. 存在 $T' > T$ 且 $T \nmid T'$ 。 ↩︎

4. 对于任意一个 $i$ 都有 $s_i = s_{i + d}$ 。 ↩︎