我的算法书 - 最小表示法

一句话算法

最小表示法让两个起点互相比赛，一旦第 $k$ 位分出胜负，就一次淘汰输家起点后面连续 $k+1$ 个不可能答案。

问题模型

给定一个长度为 $n$ 的字符串 $s$ ，把它首尾相接看成环。每个起点都能得到一个循环同构串：

s = abc
起点 0: abc
起点 1: bca
起点 2: cab

目标是找到字典序最小的循环同构串，并返回它在原串中的起点。

例如：

s = bba
循环同构: bba, bab, abb
最小表示: abb
起点: 2

核心直觉

暴力做法会枚举所有起点，两两比较，最坏 $O(n^2)$ 。

最小表示法的核心是“比较一次，淘汰一段”。

设两个候选起点为 i 和 j，它们前 k 个字符都相同，但第 k 个字符不同：

s[i + 0] == s[j + 0]
s[i + 1] == s[j + 1]
...
s[i + k - 1] == s[j + k - 1]
s[i + k] >  s[j + k]

此时从 i 开始的循环串输给了从 j 开始的循环串。不只 i 会输，i, i+1, ..., i+k 这些起点都不可能成为最小表示。

原因是每个 i+p 都能找到对应的 j+p 作为更优竞争者。

算法步骤

令 i = 0，j = 1，分别表示两个候选起点。
令 k = 0，表示当前两个候选已经匹配的长度。
比较 s[(i+k)%n] 和 s[(j+k)%n]：
- 若相等，令 k++；
- 若左边更大，i 这一段失败，令 i += k + 1；
- 若右边更大，j 这一段失败，令 j += k + 1。
每次淘汰后重置 k = 0。
若 i == j，把其中一个指针再向后移动一位。
当某个指针达到 n 或已经比较了 n 个字符，答案是 min(i,j)。

算法证明

关键引理：若 S_i 和 S_j 前 k 个字符相同，并且第 k 个字符处 S_i > S_j，那么 i, i+1, ..., i+k 都不可能是答案。

证明：

取任意偏移 $p$ ，其中 $0 \le p \le k$ 。

由于前 $k$ 个字符相同，S_{i+p} 与 S_{j+p} 在遇到第一个不同字符前，看到的是同一段对应内容。到比较到原来的失配点时：

S_i[k] > S_j[k]

因此：

S_{i+p} > S_{j+p}

也就是说，起点 i+p 至少输给了起点 j+p，所以 i+p 不可能是全局最小。

于是当 S_i > S_j 时，可以安全跳过 [i,i+k]；反过来当 S_j > S_i 时，可以安全跳过 [j,j+k]。

指针始终只向右移动，每次淘汰的起点都已证明不可能成为答案，所以最后留下的候选就是最小表示起点。

复杂度分析

设字符串长度为 $n$ 。

时间复杂度： $O(n)$ 。两个指针只向右移动，被淘汰的位置不会重新成为候选。
空间复杂度： $O(1)$ 。只需要维护 i,j,k 等常数变量。

代码实现

模板输入一个字符串，输出它的最小表示。

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

        #include <bits/stdc++.h>
using namespace std;

int minimal_rotation_pos(const string &s) {
    int n = (int)s.size();
    int i = 0;
    int j = 1;
    int k = 0;

    while (i < n && j < n && k < n) {
        char a = s[(i + k) % n];
        char b = s[(j + k) % n];

        if (a == b) {
            k++;
        } else if (a > b) {
            i += k + 1;
            if (i == j) i++;
            k = 0;
        } else {
            j += k + 1;
            if (i == j) j++;
            k = 0;
        }
    }

    return min(i, j);
}

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

    string s;
    cin >> s;

    int pos = minimal_rotation_pos(s);
    for (int i = 0; i < (int)s.size(); i++) {
        cout << s[(pos + i) % (int)s.size()];
    }
    cout << '\n';

    return 0;
}

测试用例

输入：

bba

输出：

abb

再看一个有重复周期的例子：

ababab

最小表示仍然是：

ababab

它有多个等价最小起点，模板返回其中下标最小的一个。

应用分类详解

最小表示法的本质是“在所有循环同构串中找字典序最小代表”。看到字符串可以旋转、项链、环形序列时，就应该想到它。

一、循环同构规范化

典型模式： 判断两个环形字符串是否本质相同，或需要给环形字符串一个唯一代表。

识别信号： 出现“旋转后相同”“循环移位”“环形字符串”。

核心建模： 对每个字符串求最小表示，把环形对象变成普通字符串后比较。

应用场景	经典题目	核心思路
判断旋转等价	环形字符串判等	两个串的最小表示相同则等价
项链表示	项链去重	每条项链用最小表示作为规范形

二、环形序列最小字典序输出

典型模式： 给定一个环形排列，要求从某处断开，使输出字典序最小。

识别信号： 出现“选择一个起点输出”“环形数组”“字典序最小”。

核心建模： 把序列转成字符串或可比较数组，使用最小表示法找断点。

应用场景	经典题目	核心思路
模板题	luogu-P13270	直接求最小表示起点
最小循环移位	AcWing 136	双指针淘汰候选起点

三、作为字符串比较组件

典型模式： 更大问题中需要快速比较环形状态。

识别信号： 状态有环形对称性，直接比较会产生很多重复状态。

核心建模： 先把每个环形状态规范化，再放入集合、排序或哈希表。

经典例题

1. luogu-P13270

最小表示法模板题。重点练习双指针淘汰区间的写法。

2. AcWing 136

求字符串的最小循环移位。适合作为最小表示法入门题。

3. LeetCode 1163

不是环形字符串，但也体现了“多个起点竞争，失败者批量淘汰”的思想。可以用来理解同类双指针比较模型。

参考

OI Wiki - 最小表示法