「一本通 2.1 练习 4」A Horrible Poem

形式化题目

给定一个长度为 $n$ 的小写英文字母字符串 $S$ 。给出 $q$ 次询问，每次询问给出区间 $[a, b]$ （ $1 \le a \le b \le n$ ），求子串 $S[a..b]$ 的最短循环节长度 $k$ 。即要求 $k$ 整除 $b - a + 1$ ，且 $S[a..b]$ 可由其长度为 $k$ 的前缀重复拼接而成。

字符串哈希与质因子试除法

思路

1. 循环节判定的等价条件

设子串 $T = S[a..b]$ 的长度为 $L = b - a + 1$ 。若正整数 $k$ 是 $T$ 的循环节长度，首先必须满足 $k \mid L$ 。其次， $T$ 具有长度为 $k$ 的循环节等价于： $T$ 去掉末尾 $k$ 个字符的前缀，与 $T$ 去掉开头 $k$ 个字符的后缀完全相等。即：

S[a .. b - k] = S[a + k .. b]

通过预处理字符串 $S$ 的前缀哈希值，可以在 $O(1)$ 时间内比较任意两个子串是否相同，从而在 $O(1)$ 时间内验证 $k$ 是否为一个合法的循环节。

2. 循环节性质与质因子分解

如果枚举 $L$ 的全部约数进行验证，对于每个询问开销较大。注意到：若 $k_1$ 和 $k_2$ 都是整除 $L$ 的循环节，则 $\gcd(k_1, k_2)$ 也是 $L$ 的循环节。因此， $L$ 的所有循环节长度构成的约数集合对 $\gcd$ 封闭，存在唯一的最小循环节，且其他所有合法循环节都是最小循环节的倍数。

这意味着我们可以从最大可能长度 $L$ 开始，尝试将它的各个质因子逐一除去：

对 $L$ 进行质因数分解： $L = p_1^{c_1} p_2^{c_2} \cdots p_m^{c_m}$ 。
令当前候选循环节长度 $ans = L$ 。
依次考虑每个质因子 $p$ ：若 $ans / p$ 仍然是合法循环节（即 $S[a .. b - ans/p] = S[a + ans/p .. b]$ ），则说明质因子 $p$ 可以被消去，令 $ans \leftarrow ans / p$ ；否则保留。
遍历完所有质因子后， $ans$ 即为最短循环节长度。

3. 快速质因数分解

由于 $n \le 5 \times 10^5$ ，可以预先利用线性筛（欧拉筛）预处理出每个数的最小质因数 min_p[x]。对于给定的区间长度 $L$ ，每次只需沿着 min_p[L] 不断除以对应质因数，即可在 $O(\log L)$ 时间内求出 $L$ 的所有质因子。每个质因子只做一次 $O(1)$ 的哈希检验，因此单次询问的检查次数不超过 $\sum c_i \le \log_2 n \approx 19$ 次。

图示解析

以样例中子串 abcabc（长度 $L = 6$ ， $a = 3, b = 8$ ）为例，检验过程如下：

graph TD
    A["初始长度 L = 6, 质因子分解: [2, 3]"] --> B["尝试除去质因子 2: 检验 k = 3"]
    B --> C{"S[3..5] == S[6..8]? (abc == abc)"}
    C -- "相等" --> D["成功更新 ans = 3"]
    D --> E["尝试除去质因子 3: 检验 k = 1"]
    E --> F{"S[3..7] == S[4..8]? (abcab == bcabc)"}
    F -- "不相等" --> G["保留 ans = 3"]
    G --> H["最终最短循环节 = 3"]

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 12:00
# update_at: 2026-09-30 12:00

import sys

BASE = 131
MOD = 1_000_000_007


def build_sieve(n: int) -> list[int]:
    """线性筛预处理每个数的最小质因数。"""
    min_p = list(range(n + 1))
    primes: list[int] = []
    for i in range(2, n + 1):
        if min_p[i] == i:
            primes.append(i)
        for p in primes:
            if p * i > n:
                break
            min_p[p * i] = p
            if i % p == 0:
                break
    return min_p


def get_prime_factors(x: int, min_p: list[int]) -> list[int]:
    """质因数分解，返回 x 的所有质因数列表（含重数）。"""
    factors: list[int] = []
    while x > 1:
        p = min_p[x]
        factors.append(p)
        x //= p
    return factors


def is_period(a: int, b: int, k: int, h: list[int], power: list[int]) -> bool:
    """检验长度为 k 的前缀是否为 S[a..b] 的循环节。

    S[a..b] 长度为 L = b - a + 1。
    若 k 为周期，则 S[a .. b - k] 与 S[a + k .. b] 相同。
    """
    # 子串 S[a..b-k] 的哈希值 vs 子串 S[a+k..b] 的哈希值
    h1 = (h[b - k] - h[a - 1] * power[b - k - a + 1]) % MOD
    h2 = (h[b] - h[a + k - 1] * power[b - a - k + 1]) % MOD
    return h1 == h2


def solve() -> None:
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    it = iter(input_data)
    n = int(next(it))
    s = next(it)
    q = int(next(it))

    # 预处理字符串哈希与幂次
    h = [0] * (n + 1)
    power = [1] * (n + 1)
    for i, ch in enumerate(s, 1):
        power[i] = (power[i - 1] * BASE) % MOD
        h[i] = (h[i - 1] * BASE + ord(ch)) % MOD

    min_p = build_sieve(n)

    out: list[str] = []
    for _ in range(q):
        a = int(next(it))
        b = int(next(it))
        length = b - a + 1

        factors = get_prime_factors(length, min_p)
        ans = length
        for p in factors:
            cand = ans // p
            if is_period(a, b, cand, h, power):
                ans = cand

        out.append(str(ans))

    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 02:35
 * update_at: 2026-10-05 02:35
 */

// 求子串最短循环节：字符串哈希 O(1) 检验周期 + 线性筛最小质因数分解贪心试除。
#include <cstdio>
#include <cstring>

typedef long long ll;

const int MAXN = 500005;   // 字符串最大长度
const ll MOD = 1000000007; // 哈希模数
const ll BASE = 131;       // 哈希进制

int n, q; // n <= 5e5, q <= 2e6，都在 int 范围内
char s[MAXN];     // 原字符串，下标从 1 开始
ll hsh[MAXN];     // hsh[i] = s[1..i] 的前缀哈希值
ll pw[MAXN];      // pw[i] = BASE^i mod MOD
int minp[MAXN];   // minp[x] = x 的最小质因数（线性筛预处理）
int primes[MAXN]; // 线性筛筛出的质数表（个数约 41538，开 MAXN 足够）

// ---------- 快读：一次性读入整个输入 ----------
char ibuf[1 << 25]; // 输入约 24MB，缓冲区开 32MB
int ipos = 0, ilen = 0;

// 读入一个非负整数
ll read_num() {
    while (ipos < ilen && (ibuf[ipos] < '0' || ibuf[ipos] > '9')) ipos++;
    ll x = 0;
    while (ipos < ilen && ibuf[ipos] >= '0' && ibuf[ipos] <= '9') {
        x = x * 10 + (ibuf[ipos] - '0');
        ipos++;
    }
    return x;
}

// ---------- 快写：一次性输出所有答案 ----------
char obuf[1 << 24]; // q 行答案，每行最多 7 字节，16MB 足够
int opos = 0;

void write_num(ll x) {
    char tmp[24];
    int len = 0;
    if (x == 0) tmp[len++] = '0';
    while (x > 0) {
        tmp[len++] = '0' + x % 10;
        x /= 10;
    }
    while (len > 0) obuf[opos++] = tmp[--len];
    obuf[opos++] = '\n';
}

// 取 s[l..r] 的哈希值
ll get_hash(int l, int r) {
    return (hsh[r] - hsh[l - 1] * pw[r - l + 1] % MOD + MOD) % MOD;
}

// 判断 k 是否为 s[a..b] 的循环节：
// 等价于去掉末尾 k 个字符的前缀与去掉开头 k 个字符的后缀完全相同
bool check(int a, int b, int k) {
    return get_hash(a, b - k) == get_hash(a + k, b);
}

// 线性筛预处理 [2, n] 内每个数的最小质因数
void sieve() {
    int cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes[cnt++] = i;
        }
        for (int j = 0; j < cnt && (ll)primes[j] * i <= n; j++) {
            minp[primes[j] * i] = primes[j];
            if (i % primes[j] == 0) break;
        }
    }
}

int facs[40]; // 临时存放当前区间长度的质因子（含重数，最多约 20 个）

int main() {
    ilen = fread(ibuf, 1, sizeof(ibuf), stdin);

    n = read_num();
    // 读入字符串，跳过非小写字母
    while (ipos < ilen && (ibuf[ipos] < 'a' || ibuf[ipos] > 'z')) ipos++;
    for (int i = 1; i <= n; i++) s[i] = ibuf[ipos++];
    q = read_num();

    // 预处理前缀哈希与幂次
    pw[0] = 1;
    for (int i = 1; i <= n; i++) {
        pw[i] = pw[i - 1] * BASE % MOD;
        hsh[i] = (hsh[i - 1] * BASE + s[i]) % MOD;
    }
    sieve();

    for (int t = 0; t < q; t++) {
        int a = read_num();
        int b = read_num();
        int L = b - a + 1; // 询问子串长度

        // 沿最小质因数分解 L，得到全部质因子（含重数）
        int fc = 0;
        for (int x = L; x > 1; x /= minp[x]) facs[fc++] = minp[x];

        // 贪心试除：循环节长度集合对 gcd 封闭，从 L 开始尽量除去质因子
        int ans = L;
        for (int i = 0; i < fc; i++) {
            int cand = ans / facs[i];
            if (check(a, b, cand)) ans = cand;
        }
        write_num(ans);
    }

    fwrite(obuf, 1, opos, stdout);
    return 0;
}

复杂度分析

时间复杂度：
- 线性筛与字符串哈希预处理时间复杂度为 $O(n)$ 。
- 每次询问质因数分解与哈希验证次数不超过质因子总重数 $\sum c_i = O(\log L)$ 。 $q$ 次询问总耗时 $O(q \log n)$ 。
- 总时间复杂度为 $O(n + q \log n)$ 。
空间复杂度：
- 线性筛数组、质数表、前缀哈希数组及幂次数组大小均为 $O(n)$ 。
- 总空间复杂度为 $O(n)$ 。

总结

字符串循环节的充要条件可以转化为前后缀字符串的相等性匹配，借助前缀哈希可实现 $O(1)$ 判定。
循环节的 $\gcd$ 封闭性保证了质因子贪心试除的正确性。配合线性筛预处理最小质因数，避免了全量因子枚举，将单次询问降至对数级别。