形式化题目

给定长度 $N$ 的字符串 $S$。对每个前缀长度 $i \in [2, N]$，判断 $S[1..i]$ 能否写成

若可以，求出其中最大的 $K$（即最短的循环节 $A$），并把 $(i, K)$ 作为答案。 要求所有答案按 $i$ 升序排列；若某个前缀无解则不产生答案。

正解

思路

先看朴素做法的瓶颈。 对每个 $i$，从小到大枚举循环节长度 $p \mid i$，比较 $S[1..i-p]$ 与 $S[p+1..i]$ 是否相等，第一个成立的 $p$ 就给出最大的 $K = i/p$。单个 $i$ 的 代价是 $O(i)$，全部 $i$ 加起来是 $O(N^2)$，而 $N$ 可达 $10^6$、时限 1 s，必须复用已经 算过的信息。

把「循环节」翻译成「border」。 长度 $i$ 的串 $T$，若 $p \mid i$ 且 $T[k] = T[k+p]$ 对所有 $k \leqslant i-p$ 成立，则 $T$ 的前 $i-p$ 个字符与后 $i-p$ 个字符 完全相同——也就是 $T$ 有一个长度 $i-p$ 的 border（既是真前缀又是真后缀的串）。 反过来，只要 $T$ 有长度 $i-p$ 的 border，$p$ 就是它的周期。于是

两者一一对应且方向相反，所以最短周期由最长 border 决定：

问题从「对每个前缀找周期」变成「对每个前缀求最长 border」。

一趟线性求出所有 $\pi(i)$。 border 有一条很好用的性质：border 的 border 还是 border。于是求 $\pi(i)$ 时不用重看整段字符，而是从 $\pi(i-1)$ 出发沿失配链 $\pi(i-1) \to \pi(\pi(i-1)) \to \cdots$ 往回跳，找到第一个满足 $S[t+1] = S[i]$ 的 $t$，取 $\pi(i) = t+1$；跳到 0 还没匹配上就取 $\pi(i) = 0$。这正是 KMP 失配数组的常规求法， 它的线性来自一个简单的势能论证：失配游标每轮至多加一，而 while 每次回跳都让它严格 减小，总回跳次数不超过总增加次数，所以整趟扫描是 $O(N)$。

从 $\pi$ 读出答案的两个条件。 已知 $p_{\min}$ 后，还要确认 $S[1..i]$ 真的能被它 整分成若干段：

• $p_{\min} \mid i$ 是必要条件。设 $S[1..i] = A^K$（$|A| = p < i$），则 $p$ 也是周期， 由 $p_{\min}$ 最小得 $p_{\min} \leqslant p$。又 $p \mid i$ 且 $p < i$ 说明 $p \leqslant i/2$，于是 $p_{\min} + p \leqslant i$。此时用周期引理（$p, q$ 都是长度 $i$ 串的周期且 $p + q \leqslant i$ 时 $\gcd(p, q)$ 也是周期）：$\gcd(p_{\min}, p)$ 是周期，而它 $\leqslant p_{\min}$，由 $p_{\min}$ 的 最小性只能是 $\gcd(p_{\min}, p) = p_{\min}$，即 $p_{\min} \mid p$；再由 $p \mid i$ 传递得到 $p_{\min} \mid i$。
• $p_{\min} \mid i$ 也是充分条件：把 $S[1..i]$ 按 $p_{\min}$ 切成 $i / p_{\min}$ 段， 由周期性每一段都等于首段，于是它就是首段的重复，$K = i / p_{\min}$。

为什么取 $p_{\min}$ 就得到最大的 $K$。 重复次数 $K = i / p$ 关于 $p$ 严格递减，所以只要 让 $p$ 取满足条件的最小值即可。上面两段表明「满足条件」等价于「$p$ 是周期且 $p \mid i$」， 而最短周期 $p_{\min}$ 本身就在其中（已证整除），且没有任何更小的周期，故它给出的 $K = i / p_{\min}$ 就是最大值。再加上题面的 $K > 1$ （等价于 $p_{\min} < i$，也等价于 $\pi(i) > 0$），输出条件收敛成一条规则：

第一条管「$K > 1$」，第二条管「能否整分」，两者都只用到同一个量 $i - \pi(i)$。特别地， 输出条件不需要枚举其它周期长度：不满足 $p_{\min} \mid i$ 的前缀，换成任何更大的周期 $p \mid i$ 也不可能成立。

用样例 aabaabaabaab 走一遍。 下表列出每个前缀的 $\pi$、最短周期 $p$ 与整除判断 （$\pi(i)$ 用 1 起的前缀长度计）：

观察 $i = 3$：$p = 3$ 确实整除 $3$，但 $\pi(3) = 0$ 意味着最长 border 长度为 0， $K$ 只能是 1，必须排除——这正是条件里要点明 $\pi(i) > 0$ 的原因。而 $i = 4, 5$ 的 $p$ 也是 3，却因为 $3 \nmid 4$、$3 \nmid 5$ 被判掉：aaba、aabaa 都不是 aab 的整数倍 重复。输出与样例的 2 2 / 6 2 / 9 3 / 12 4 完全一致。

代码

prefix_function 就是上面那趟线性建表，j 是失配链游标；repeats 把「最短周期 + 两个输出条件」写成生成器 + 推导式：period < length 负责排除 $K = 1$， length % period == 0 负责整除，二者分别对应上面那两条判据；solve 只做读入、 按组调用与拼接输出。

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#!/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-10-01 11:41
# update_at: 2026-10-01 11:50

import sys


def prefix_function(s: bytes) -> list[int]:
    """KMP 失配数组：nxt[i] 是 s[:i+1] 最长的「真前缀 = 真后缀」的长度，下标从 0 起。"""
    n = len(s)
    nxt = [0] * n
    for i in range(1, n):
        j = nxt[i - 1]
        while j and s[i] != s[j]:  # 失配就沿失配链回跳，直到能接上或跳到 0
            j = nxt[j - 1]
        if s[i] == s[j]:
            j += 1
        nxt[i] = j
    return nxt


def repeats(s: bytes) -> list[tuple[int, int]]:
    """每个「恰好由循环节拼成的前缀」(前缀长度 length, 重复次数 k)，按 length 升序。"""
    nxt = prefix_function(s)
    # 长度 length 的最短周期 period = length - nxt[length-1]；
    # period < length 说明循环节不是前缀本身，即 k > 1；
    # period 再整除 length 时，该前缀恰好是 k = length/period 个 period 的重复。
    cycles = ((length, length - nxt[length - 1]) for length in range(2, len(s) + 1))
    return [
        (length, length // period)
        for length, period in cycles
        if period < length and length % period == 0
    ]


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())  # token 混有字符串 s，不能整体 map(int)
    out: list[str] = []
    case = 0
    while n := int(next(data)):  # 每组先读长度 n，读到 0 结束
        case += 1
        s = next(data)
        out.append(f"Test case #{case}")
        out += [f"{length} {k}" for length, k in repeats(s)]  # 输入保证 len(s) == n，无需再截断
        out.append("")  # 每组末尾的空行，同时也是下一组的前导空行

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-06 15:31
 * update_at: 2026-10-06 15:31
 */
// main.cpp：KMP 前缀函数求每个前缀的最短周期。
// 长度为 i 的前缀，最短周期 period = i - nxt[i]（nxt[i] 是最长 border 长度）；
// 当 nxt[i] > 0（保证 K > 1）且 period 整除 i 时，前缀恰好由 K = i / period 个循环节拼成。

#include <cstdio>
#include <cstring>

typedef long long ll;

const int MAXN = 1000005;

int n;              // 当前测试数据的字符串长度
char s[MAXN];       // 字符串，下标从 1 开始
int nxt[MAXN];      // nxt[i]：s[1..i] 的最长「真前缀 = 真后缀」长度（border）

// 一趟线性求出整个 nxt 数组：从 nxt[i-1] 沿失配链回跳，看能否接上 s[i]。
void get_next() {
    nxt[1] = 0;
    int j = 0; // j 是当前尝试的 border 长度，也是失配链游标
    for (int i = 2; i <= n; i++) {
        while (j && s[i] != s[j + 1]) j = nxt[j]; // 失配就回跳到更短的 border
        if (s[i] == s[j + 1]) j++;
        nxt[i] = j;
    }
}

int main() {
    int case_id = 0;
    while (scanf("%d", &n) == 1 && n != 0) {
        scanf("%s", s + 1);
        get_next();

        printf("Test case #%d\n", ++case_id);
        for (int i = 2; i <= n; i++) {
            int period = i - nxt[i]; // 最短周期 = 长度 - 最长 border 长度
            // nxt[i] > 0 保证 K > 1；period 整除 i 保证前缀能被循环节整分
            if (nxt[i] > 0 && i % period == 0)
                printf("%d %d\n", i, i / period);
        }
        printf("\n"); // 每组数据末尾输出一个空行
    }
    return 0;
}

复杂度

• 时间复杂度：总长 $N$ 的一组数据，建失配数组与扫描输出各 $O(N)$，输出本身的字符量 为 $O(N \log N)$（每行含 $O(\log N)$ 位的长度和 $K$）。多组数据为 $O\!\left(\sum_j N_j \log N_j\right)$，与标准 C++ 正解同阶。
• 空间复杂度：失配数组 $O(N)$ 个整数，另加读入缓冲与输出行，合计 $O(N)$。 实测最大一组 $N = 10^6$ 峰值约 73 MB，在 128 MB 之内。

总结

本题的落点是「用前缀函数把周期问题变成查表」：

1. 朴素做法对每个前缀重新比较，$O(N^2)$；瓶颈在于前缀之间的信息没有复用；
2. 关键等价：$T$ 有周期 $p$ $\iff$ $T$ 有长度 $|T| - p$ 的 border，于是最短周期 = $i - \pi(i)$；
3. $\pi(i)$ 只需从 $\pi(i-1)$ 沿失配链回跳即可求出，一趟扫描 $O(N)$；
4. 输出条件收敛为「$\pi(i) > 0$ 且 $i - \pi(i)$ 整除 $i$」，前者管 $K > 1$，后者管能否整分。

真实数据 data/a.in（共 7 组，$N$ 最大 $10^6$）与 data/a.out 逐字节一致，整份数据 跑完约 0.27 s、峰值约 73 MB，远低于 1000 ms / 128 MB。

图示解析

这张图串起从题面到代码的主线：

1
2
3
4
5
6
7
8前缀 S[1..i]，问是否 = A^K (K>1) 且 K 最大
`- 枚举 p | i 逐字符比较  ->  O(N^2)，瓶颈是“每个前缀都从零重算”
   `- 关键等价：周期 p  <->  border 长度 i - p
      `- 于是 最短周期 p_min = i - π(i)      （π = 最长 border 长度）
         |- π(i) 由 π(i-1) 沿失配链回跳得到  ->  一趟 O(N)
         |- 整除判据：p_min | i  <=>  字符串能被整分
         `- K>1 判据：π(i) > 0  <=>  p_min < i
            `- 输出 (i, i / p_min)，下标升序天然有序

逐个节点看：第一行是朴素做法，第二行把它压成「求 border」，第三行给出唯一的判定量 $p_{\min}$，最后两行是输出条件与顺序。整条链上没有任何一步需要额外的字符串比较或排序。

下面用样例第一组 aaa 说明 $\pi$ 数组是怎么被读出来的。先看下标含义：代码里的 nxt[i] 存的是前缀 s[0..i]（0 起）的最长 border 长度，与题面的 1 起前缀长度差 1。

nxt 一路增长到 n-1，是因为每个更长的前缀都能把前一个 border 接上同一个字符， 于是 period 恒为 1、K 恒等于长度——全同字符串就是这样被一路输出的。