[BalticOI 2009] Radio Transmission 无线传输

这道题目虽然是 KMP 算法的经典例题（利用 next 数组求最小循环节），但完全可以使用 字符串哈希 (String Hash) 来解决。

核心思路

题目要求找到构成字符串 $S$ 的最短循环节长度 $X$。 根据字符串周期性的性质，有一个非常重要的结论：

如果一个长度为 $L$ 的字符串 $S$ 有一个长度为 $X$ 的循环节，那么 $S$ 的长度为 $L-X$ 的前缀一定等于 $S$ 的长度为 $L-X$ 的后缀。

解释

假设字符串 $S$ 是 cabcabca ($L=8$)。 我们尝试移动这个字符串：

• 原串：cabcabca
• 右移3位： cabcabca
• 重叠部分：cabca (长度为 $5 = 8-3$)

如果移位后的重叠部分完全相同，说明移动的距离 $X$ 就是一个可能的循环节长度。 为了使循环节 $X$ 最小，我们需要重叠的部分（即“前缀=后缀”）的长度尽可能大。

算法步骤：

1. 计算整个字符串的 Hash 值。
2. 从大到小枚举可能的“公共前后缀长度” len (从 $L-1$ 到 $1$)。
3. 一旦发现 Hash(前缀len) == Hash(后缀len)，通过公式 $X = L - len$ 得到的 $X$ 即为最小循环节长度。
4. 直接输出 $X$ 并结束。

C++ 代码实现 (Hash 版本)

        
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

        #include <iostream>
#include <vector>
#include <string>

using namespace std;

typedef unsigned long long ull;

const int MAXN = 1000005;
const int P = 131; //或者 13331

ull h[MAXN]; // 哈希数组
ull p[MAXN]; // P的次方数组
char s[MAXN]; // 字符串数组（下标从1开始）
int L;

// 初始化哈希
void init_hash() {
    p[0] = 1;
    for (int i = 1; i <= L; ++i) {
        h[i] = h[i - 1] * P + s[i]; // 计算前缀哈希
        p[i] = p[i - 1] * P;        // 预处理 P 的幂
    }
}

// O(1) 获取子串 s[l...r] 的哈希值
ull get_hash(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
    // 优化输入输出
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> L;
    cin >> (s + 1); // 从下标 1 开始读入

    init_hash();

    // 我们要找最小的循环节长度 X
    // 这等价于找最长的公共前后缀长度 len
    // 关系：X = L - len
    // 所以 len 从 L-1 开始向下枚举，找到的第一个匹配就是最大的 len，对应的 X 就是最小的
    
    int ans = L; // 最坏情况，循环节是它自己

    for (int len = L - 1; len >= 1; --len) {
        // 检查长度为 len 的前缀是否等于长度为 len 的后缀
        // 前缀区间: [1, len]
        // 后缀区间: [L - len + 1, L]
        if (get_hash(1, len) == get_hash(L - len + 1, L)) {
            ans = L - len;
            break; // 找到了最长的 border，对应的就是最短的周期，直接退出
        }
    }

    cout << ans << endl;

    return 0;
}

    

图解说明

以样例 cabcabca 为例 ($L=8$)：

我们从最大的可能重叠长度 len = 7 开始尝试：

1. len = 7: 前缀 cabcabc vs 后缀 abcabca。不相等。
2. len = 6: 前缀 cabcab vs 后缀 bcabca。不相等。
3. len = 5: 前缀 cabca vs 后缀 cabca。相等！

此时找到的最长公共前后缀长度 len = 5。 最短循环节长度 $X = L - len = 8 - 5 = 3$。 验证：abc 重复确实能覆盖 cabcabca。

复杂度分析

• 时间复杂度: $O(L)$。
  • 预处理哈希需要遍历一次字符串。
  • 枚举 len 最多遍历 $L$ 次，每次哈希比较是 $O(1)$ 的。
• 空间复杂度: $O(L)$。
  • 需要存储字符串、哈希数组和幂次数组。

总结

虽然 KMP 的 next 数组（$L - next[L]$）是此题的标准解法，但 Hash 方法逻辑更直观（寻找 Prefix == Suffix），且在 $10^6$ 的数据规模下使用 unsigned long long 自然溢出通常足够通过，且极难发生哈希冲突。

这是一个非常好的直觉性问题。作为一个普通人，不需要去推导复杂的数学公式，我们只需要用**“平移”和“重叠”**的视角来看待这件事，就能瞬间明白了。

核心结论其实就是一句话：“循环”就意味着“平移后能重合”。

我们分三步来直观理解：

第一步：什么是“循环节”？

想象你在铺地砖，或者盖印章。 如果你有一个图案（比如 abc），你不断地重复它：abc abc abc… 这就叫有循环节。

如果一个字符串 $S$ 的循环节长度是 $X$，这意味着什么？ 这意味着：如果你把这个字符串向右平移 $X$ 格，它重叠的部分会和原来一模一样。

比如 abcabcabc，循环节长度 $X=3$。

原串：      abcabcabc
向右平移3格：   abcabcabc

你看，中间重叠的部分是不是完全吻合？

第二步：观察“平移”后的结构

让我们把这个平移的过程画得更清楚一点。假设字符串总长是 $L$，循环节长度是 $X$。

我们将原字符串复制一份，放在下面，然后向右推 $X$ 格：

• 上面的串（原串）：露出左边的头（长度 $X$），剩下右边的一大段（长度 $L-X$）。
• 下面的串（平移串）：露出右边的尾（长度 $X$），剩下左边的一大段（长度 $L-X$）。

重点来了： 因为它是循环的，所以上下重叠的那部分（长度为 $L-X$）必须完全相等。

第三步：谁等于谁？

让我们看看重叠的那部分分别代表什么：

1. 对于上面的串：因为我们向右错开了头部的 $X$ 个字符，所以重叠的部分是它的后缀（即去掉开头 $X$ 个字符剩下的部分）。
2. 对于下面的串：因为它是向右平移进来的，重叠的部分是它的前缀（即去掉末尾 $X$ 个字符剩下的部分）。

结论： 既然上下重叠部分必须相等，那么： 下面的前缀 = 上面的后缀。

也就是： 长度为 $L-X$ 的前缀 = 长度为 $L-X$ 的后缀。

举个具体的例子

用你题目中的 cabcabca （长度 $L=8$）来验证一下。 我们看看如果循环节 $X=3$（即 cab 是循环节）会发生什么：

1. 拿两个一样的字符串： A: cabcabca B: cabcabca

2. 把 B 向右平移 3 格 ($X=3$)：

A (原串):    cabcabca
              |||||  <-- 这一段必须完全重合
B (平移后):     cabcabca

3. 观察重叠区域（中间 5 个字符，即 $8-3=5$）：

• 在 A 中，重叠的是 abcabca 的后 5 位 -> abcca ? 不对，是 bcabca。
  • A 的后缀 (后5位): bcabca
• 在 B 中，重叠的是 cabcabca 的前 5 位 -> cabca。
  • B 的前缀 (前5位): cabca

等一下！ 在这个例子里： 后缀 bcabca $\neq$ 前缀 cabca。 所以，$X=3$ 不是它的循环节！ 我们的直觉验证了这一点。

再试一个真正的循环串：abcabcabc ($L=9, X=3$)

A:    abcabcabc
         ||||||  (重叠长度 9-3=6)
B:       abcabcabc

• A 的重叠部分（后缀）：abcabc
• B 的重叠部分（前缀）：abcabc
• 相等！

所以结论成立：只要是循环的，那么 前缀(L-X) 一定等于 后缀(L-X)。

总结 (人话版)

想要知道一个字符串是不是每 $X$ 个字符重复一次？ 你就把它掐头（去掉前 $X$ 个）和去尾（去掉后 $X$ 个）。 如果掐头剩下的部分和去尾剩下的部分长得一模一样，那它就是以 $X$ 为周期循环的。

• 去尾 = 前缀
• 掐头 = 后缀

这就是为什么代码里要找 Hash(前缀) == Hash(后缀) 的原因。

我的总结

• 长度为x的循环节,比如abc,如果是从循环节开头的字符串,平移x后,重叠
• [abcabc] abc是循环节,那么bca,cab也可以看成循环节

当然可以暴力验证

        
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

        #include <iostream>
#include <algorithm>
using namespace std;

typedef unsigned long long ull;
const int MAXN = 1000005;
const int P = 131;

ull h[MAXN], p[MAXN];
char s[MAXN];
int n;

void init_hash() {
    p[0] = 1;
    for (int i = 1; i <= n; ++i) {
        h[i] = h[i - 1] * P + s[i];
        p[i] = p[i - 1] * P;
    }
}

ull get_hash(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> (s + 1);
    init_hash();

    // 暴力枚举循环节长度 len
    for (int len = 1; len <= n; ++len) {
        bool ok = true;
        int _len = n-len;
        ull pre = get_hash(1, _len);
        ull suf = get_hash(n-_len+1 ,n);
        if( pre == suf) {
            cout << len << endl;
            break;
        }
        
    }

    return 0;
}

    

暴力枚举

你的直觉非常敏锐！完全可以使用这种暴力验证的方法。

实际上，这种看似“暴力”的方法，在这个数据规模下不仅可行，而且效率非常高。我们称之为调和级数枚举。

1. 你的思路逻辑

你的想法是：

1. 从小到大枚举可能的循环节长度 len（从 1 开始）。
2. 对于每一个 len，把原字符串切成一块一块：[1, len], [len+1, 2*len], …
3. 利用 Hash $O(1)$ 判断每一块是否都和第一块 [1, len] 相同。
4. 注意细节：由于题目说原串是循环串的子串，所以最后一块可能不完整。最后一块只需要是第一块的前缀即可。

2. 为什么它不会超时？（复杂度分析）

很多同学看到“两层循环”就会担心是 $O(N^2)$，但这里是个特例。

• 当 len = 1 时，内层循环跑 $N$ 次。
• 当 len = 2 时，内层循环跑 $N/2$ 次。
• 当 len = 3 时，内层循环跑 $N/3$ 次。
• …
• 当 len = N 时，内层循环跑 $1$ 次。

总运算次数是：

这是著名的调和级数。它的和近似于 $\ln N$。 所以总时间复杂度是 $O(N \log N)$。

对于 $N=10^6$，$\log N \approx 20$，$20 \times 10^6 = 2 \times 10^7$ 次运算，计算机 1 秒大概能跑 $10^8$ 次，所以完全能过！

3. 代码实现 (暴力验证版)

这是按照你的思路写的代码，比找“前后缀”的逻辑更容易理解：

        
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

        #include <iostream>
#include <algorithm>
using namespace std;

typedef unsigned long long ull;
const int MAXN = 1000005;
const int P = 131;

ull h[MAXN], p[MAXN];
char s[MAXN];
int n;

void init_hash() {
    p[0] = 1;
    for (int i = 1; i <= n; ++i) {
        h[i] = h[i - 1] * P + s[i];
        p[i] = p[i - 1] * P;
    }
}

ull get_hash(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> (s + 1);
    init_hash();

    // 你的思路：暴力枚举循环节长度 len
    for (int len = 1; len <= n; ++len) {
        bool ok = true;
        
        // 验证后面的每一段
        // j 是每一段的起点：1, 1+len, 1+2len...
        for (int j = 1; j <= n; j += len) {
            // 计算当前这一段的长度
            // 通常是 len，但最后一段可能不足 len
            int cur_len = min(len, n - j + 1);
            
            // 核心验证：
            // 当前段的 Hash vs 第一段对应长度的前缀 Hash
            if (get_hash(j, j + cur_len - 1) != get_hash(1, cur_len)) {
                ok = false;
                break; // 这一段对不上，说明 len 不行，直接跳出内层循环
            }
        }

        if (ok) {
            cout << len << endl;
            return 0; // 因为是从小到大枚举，找到的第一个就是最短长度
        }
    }

    return 0;
}

    

4. 这个方法的优缺点

优点：

1. 符合直觉：非常容易想到，逻辑就是“循环”定义的直接翻译。
2. 不容易写错：不需要推导“前缀=后缀”那个数学结论，也不容易搞错边界。
3. 够快：虽然理论上比 $O(N)$ 慢一点点，但在竞赛中几乎没有区别。

缺点：

1. 处理尾巴：必须小心处理最后一段不完整的情况（代码中的 min(len, n - j + 1)）。如果忘了这一点，代码就会在最后一块出错。

总结： 你的思路非常棒！在考场上，这种 $O(N \log N)$ 的暴力验证法往往比推导 $O(N)$ 的数学性质更安全、更稳妥。