周期
题目描述
本题来自 AcWing 143：给定一个字符串 s，对于每个前缀 s[1..i]（1 ≤ i ≤ n），求出它的最小循环元长度以及循环次数。
KMP next 数组回顾
next[i] 的定义是：字符串 s[1..i] 的最长相等真前后缀的长度。也就是说，令 j = next[i]，则 s[1..j] = s[i-j+1..i]，且 j 是所有满足此条件的值中最大的。
核心观察
令 m = i - next[i]，j = next[i]。
我们将前缀 s[1..i] 分成三段：
- 前段 A：s[1..m]，长度 m
- 中段 B：s[m+1..j]，长度 j - m（即前后缀重叠的部分）
- 后段 C：s[j+1..i]，长度 i - j = m
因为 next[i] = j，所以前缀 s[1..j] = 后缀 s[m+1..i]。对齐方式如下：
1
2
3
4
5
6
| 位置： 1 ... m | m+1 ... j | j+1 ... i |
| ----------------- ||------------| |----------|
前缀： s[1] ... s[m] s[m+1] ... s[j]
s[m+1] ... s[j] s[j+1] ... s[i]
|================|
中段 B 自重复
代入具体例子来理解：
1
2
3
4
5
6
7
8
9
10
11
例：s = "ababab"，i = 6，next[6] = 4，m = 2，j = 4
前缀 s[1..4] = "abab" = 后缀 s[3..6]
位置： 1 2 3 4 5 6
|-----|--------|
| 前缀： a b | a b | s[1..4] |
| ------------------ | ---- |
| 后缀： a b | a b | s[3..6] |
= = = =
a b = a b ← 重叠区 s[3..4] = s[1..2]
证明：最小循环元长度 = i - next[i]
假设最小循环元长度为 len。我们证明 len = m = i - next[i]。
第一步：len 必须将中段 B 的长度 (j - m) 整除
中段 B = s[m+1..j] 既是前缀 s[1..j] 的前 j-m 个字符，也是后缀 s[m+1..i] 的后 j-m 个字符。如果整个串 s[1..i] 有周期 len，那么 s[1..j] 也有周期 len，B 作为 s[1..j] 的前缀，其长度必须是 len 的整数倍——否则 B 的首尾会出现不匹配，与 B 同时出现在前缀和后缀中矛盾。
第二步：反证法证明 len = m
假设 len ≠ m，分两种情况讨论：
情况1：假设 len < m
如果最小周期 len 比 m 还小，那么前段 A（长度 m）包含至少一个完整周期。由于 B 的起始位置 m+1 也是周期的对齐点，B 的结束位置 j = m + (j-m) 也是周期的对齐点。这意味着 s[1..j+len] 也是 s 的前缀且等于后缀 s[len+1..i+len]，从而存在长度 > j 的公共前后缀，与 next[i] = j（j 是最长相等真前后缀长度）矛盾。
图示说明：
1
2
3
4
5
6
7
8
9
10
假设 len < m，周期对齐如下：
位置： 1 ... len ... m ... j ... i
|--------|--------|------|------|
前缀： s[1] ... s[len] ... s[m] ... s[j]
|======================|
后缀： s[1] ... s[m] ... s[j]
|======================|
重叠区延伸到 j+len > j，
与 next[i]=j 矛盾
情况2：假设 len > m
如果最小周期 len 比 m 还大，那么重叠区 B 的长度 j - m 就小于 len，B 不可能被 len 整除（不够一个完整周期）。但另一方面，s[1..j] 被 len 整除地划分（因为 s[1..j] 是 s[1..i] 的前缀，继承周期性），所以 s[1..j] 可以被 len 整除地划分。由 s[1..j] = s[m+1..i]，后段 s[j+1..i] 也必须有同样的周期结构。但后段长度 = i - j = m < len，不够一个完整周期，矛盾。
图示说明：
1
2
3
4
5
6
7
8
9
假设 len > m，周期对齐如下：
位置： 1 ... m ... j ... i
|--------|------|------|
前缀： s[1] ... s[m] ... s[j]
s[m+1] ... s[j] s[j+1] ... s[i]
|----------------|
后段 s[j+1..i] 长度 = m < len，
不够一个完整周期，矛盾
综上，len = m = i - next[i]。
结论
对于每个前缀 s[1..i]，令 m = i - next[i]：
- 若 m 整除 i，则该前缀的最小循环元长度为 m，循环次数为 i / m
- 若 m 不整除 i，则该前缀不是纯周期串，最小循环元长度为 i，循环次数为 1
算法步骤
- 预处理 next 数组，时间复杂度 O(n)
- 对每个 i（1 ≤ i ≤ n），计算 m = i - next[i]
- 若 m 整除 i，输出 m 和 i/m；否则输出 i 和 1
代码实现
#include
const int maxn = 1000002; // it is 1000000 + 1 + 1 char str[maxn]; int nex[maxn];
int main() { int cnt = 0; int n = 0;
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
while (true) {
scanf("%d", &n);
if (!n) {
goto flag_end;
}
printf("Test case #%d\n", ++cnt);
scanf("%s", str + 1);
nex[0] = nex[1] = 0;
for (int i = 2, j = 0; i <= n; ++i) {
while (j > 0 && str[i] != str[j + 1]) {
j = nex[j];
}
if (str[i] == str[j + 1]) {
++j;
}
nex[i] = j;
const bool circular_element_exits = (i % (i - nex[i]) == 0) && nex[i] > 0;
if (circular_element_exits) {
printf("%d %d\n", i, i / (i - nex[i]));
}
}
printf("\n");
}
flag_end: return 0; }
