形式化题目

给定一个长度为 $L$ 的字符串 $S$。将 $S$ 视为环形字符串，定义起始于下标 $p$（$0 \leqslant p < L$）的循环同构串为顺时针依次读取 $L$ 个字符构成的字符串。

求所有 $L$ 个循环同构串中字典序最小的串在原字符串中的起始下标（0-indexed）。若存在多个起始位置对应的同构串字典序相同，输出最小的起始下标。

正解

思路

将环形字符串倍长为 $S' = S + S$，长度为 $2L$。从任意下标 $p \in [0, L-1]$ 开始的长度为 $L$ 的子串即对应从 $p$ 出发的循环同构串。

若使用朴素比较，两两对比候选子串需要 $O(L^2)$ 时间。在 $L \leqslant 100\,000$ 的约束下会超时。我们采用双指针最小表示法（Minimum Representation）优化至 $O(L)$：

维护两个候选起点指针 $i, j$（初始 $i = 0, j = 1$）与当前匹配的公共前缀长度 $k$（初始 $k = 0$）：

1. 比较 $S'[i + k]$ 与 $S'[j + k]$：
   • 若相等，说明当前公共前缀仍相同，令 $k \leftarrow k + 1$。
   • 若 $S'[i + k] > S'[j + k]$，说明在偏移量 $k$ 处，起点 $i$ 劣于起点 $j$。由于两串在 $[0, k-1]$ 范围内的字符完全一致，对于任意偏移量 $p \in [0, k]$，从 $i + p$ 出发的子串在第 $k - p$ 位字符上必然劣于从 $j + p$ 出发的子串。因此区间 $[i, i + k]$ 内的所有起点都不可能成为全局最优解，可以直接淘汰。令 $i \leftarrow i + k + 1$；若此时 $i = j$，则令 $i \leftarrow i + 1$ 保持指针分离，并将 $k$ 重置为 $0$。
   • 若 $S'[i + k] < S'[j + k]$，同理直接淘汰区间 $[j, j + k]$ 内的所有起点，令 $j \leftarrow j + k + 1$；若 $j = i$ 则令 $j \leftarrow j + 1$，并将 $k$ 重置为 $0$。
2. 循环直到 $i \geqslant L$、$j \geqslant L$ 或 $k \geqslant L$ 终止，返回 $\min(i, j)$。

下图展示了在偏移量 $k$ 处发现 $S'[i+k] > S'[j+k]$ 时，区间 $[i, i+k]$ 被批量淘汰并跳步的过程：

graph TD
    subgraph S'[i .. i+k]
        A["i"] --> A1["i + 1"]
        A1 --> A2["..."]
        A2 --> Ak["i + k: 字符较差（淘汰整个区间）"]
    end
    subgraph S'[j .. j+k]
        B["j"] --> B1["j + 1"]
        B1 --> B2["..."]
        B2 --> Bk["j + k: 字符更优"]
    end
    Ak -.->|跳步| NextI["新起点 i' = i + k + 1"]

代码

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#!/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-07-05 21:47
# update_at: 2026-07-05 21:47

import sys


def min_cyclic_shift(s: str) -> int:
    """求长度为 n 的字符串 s 的最小表示法起始下标（0-indexed）。"""
    n = len(s)
    doubled = s + s
    i, j, k = 0, 1, 0

    while i < n and j < n and k < n:
        diff = ord(doubled[i + k]) - ord(doubled[j + k])
        if diff == 0:
            k += 1
        elif diff > 0:
            i += k + 1
            i += int(i == j)  # 保证两个候选起点不重合
            k = 0
        else:
            j += k + 1
            j += int(i == j)  # 保证两个候选起点不重合
            k = 0

    return min(i, j)


def solve() -> None:
    it = iter(sys.stdin.buffer.read().split())
    first = next(it, None)
    if first is None:
        return
    L = int(first)
    s = next(it).decode()
    print(min_cyclic_shift(s))


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
51
52
53
54
55/**
 * 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 13:03
 * update_at: 2026-10-06 13:03
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

typedef long long ll;

ll len;          // 环形字符串的长度 L
char s[MAXN];    // 存放原字符串（0-indexed，读入时复制两遍成倍长串）
char t[2 * MAXN]; // 破环成链后的字符串 t = s + s

// 最小表示法：返回字典序最小的循环同构串的起始下标（0-indexed）。
// 两个候选起点 i、j 一起向后比，失配时利用已匹配的 k 个公共前缀
// 把劣势区间 [x, x+k] 整段跳过，保证总复杂度 O(L)。
ll min_representation() {
    ll i = 0, j = 1, k = 0;
    while (i < len && j < len && k < len) {
        if (t[i + k] == t[j + k]) {
            k++; // 当前公共前缀还在继续，继续往后比
        } else if (t[i + k] > t[j + k]) {
            // i 劣于 j：[i, i+k] 里的每个起点都必然劣于 j 平移同样的距离
            i = i + k + 1;
            if (i == j) i++; // 两个候选起点不能重合
            k = 0;
        } else {
            // j 劣于 i：同理整段淘汰 [j, j+k]
            j = j + k + 1;
            if (j == i) j++;
            k = 0;
        }
    }
    // 活下来的那个指针就是最优起点，取较小者
    return min(i, j);
}

int main() {
    scanf("%lld", &len);
    scanf("%s", s);

    // 破环成链：t = s + s，长度 2L，比较时用 t 上的子串代替环形读取
    for (ll i = 0; i < len; i++) {
        t[i] = s[i];
        t[i + len] = s[i];
    }

    printf("%lld\n", min_representation());
    return 0;
}

复杂度

• 时间复杂度：$\mathcal{O}(L)$。指针 $i$ 与 $j$ 每次跳步都至少推进 $k + 1$，两个指针均单调向后移动且不超过 $2L$，$k$ 匹配的总递增次数受指针跳跃次数所限，因此总体字符比较次数不超过 $2L$。
• 空间复杂度：$\mathcal{O}(L)$。存储倍长字符串 $S'$ 占用 $\mathcal{O}(L)$ 内存，辅助变量占用 $\mathcal{O}(1)$ 空间。

总结

• 环形问题的标准第一步是「破环成链」，即把原串自身拼接一次得到倍长串。
• 最小表示法的精髓在于利用已匹配的公共前缀信息批量跳过劣势区间，从而将原本平方阶的双重比较降至严格线性时间。