[SEERC 2003 / USACO5.5] 隐藏口令 Hidden Password

题意

给一个长度为 n 的小写字母字符串，把它看成一个环。

从任意位置出发，顺时针读满 n 个字符，就能得到一个循环位移后的字符串。

题目要求在这 n 个循环位移中，找到字典序最小的那个，并输出它对应的起点下标。

思路

先看一个可以直接验证想法的朴素解：

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;

int n;
string s;

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

    cin >> n;
    cin >> s;

    int best = 0;
    string best_str = s; // 当前字典序最小的循环串

    // brute.cpp：直接枚举所有旋转，找字典序最小的那个。
    // 复杂度是 O(n^2)，只适合小数据验证。
    for (int start = 1; start < n; start++) {
        string cur = s.substr(start) + s.substr(0, start);
        if (cur < best_str) {
            best_str = cur;
            best = start;
        }
    }

    cout << best << '\n';
    return 0;
}

brute.cpp 直接枚举每个起点，构造对应的循环串，然后取字典序最小值。

这个思路很好懂，但复杂度最坏是 $O(n^2)$ ，对于 n <= 5 * 10^6 明显不够。

真正的关键在于：比较两个候选起点 i 和 j 时，如果前面已经有一段长度为 k 的公共前缀，而第 k+1 个字符第一次分出大小，那么较大的那一侧不只是当前起点不行，连着后面的 k 个起点也都可以一起淘汰。

于是我们把字符串复制一遍，得到 t = s + s。这样从任意位置开始的循环串，都可以视作 t 中一个长度为 n 的连续区间。

接着维护三个量：

i：第一个候选起点
j：第二个候选起点
k：这两个候选已经匹配上的公共前缀长度

循环比较 t[i + k] 和 t[j + k]：

相等：继续比较下一位
不等：较大的那个起点整体后移 k + 1

这样每次都能整段删掉一批不可能成为答案的候选位置，总复杂度就降成了 $O(n)$ 。

实现时还有两个细节：

如果移动后 i == j，要把后面的那个再加一，保证始终比较两个不同候选
如果存在多个完全相同的最优循环位移，最后输出 min(i, j)，也就是最小下标

代码

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
45
46
47
48
49
50
51
52
53
54#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5000005;

int n;
char s[MAXN];     // 原字符串
char t[MAXN * 2]; // 把字符串复制一遍，方便按区间比较循环位移

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

    cin >> n;
    cin >> s;

    for (int i = 0; i < n; i++) {
        t[i] = s[i];
        t[i + n] = s[i];
    }
    t[n + n] = '\0';

    int i = 0; // 当前第一个候选起点
    int j = 1; // 当前第二个候选起点
    int k = 0; // 已经比较过的公共前缀长度

    // 最小表示法：
    // 比较从 i 和 j 开始的两个循环串，淘汰较大的那个起点。
    while (i < n && j < n && k < n) {
        if (t[i + k] == t[j + k]) {
            k++;
            continue;
        }

        if (t[i + k] > t[j + k]) {
            // 以 i 开头的串更大，那么 [i, i + k] 这些起点都不可能更优。
            i = i + k + 1;
            if (i == j) {
                i++;
            }
        } else {
            // 同理，淘汰以 j 为起点的一段候选。
            j = j + k + 1;
            if (i == j) {
                j++;
            }
        }
        // 重新比较新的两个候选。
        k = 0;
    }

    cout << min(i, j) << '\n';
    return 0;
}

复杂度

时间复杂度：

$O(n)$

空间复杂度：

$O(n)$

额外空间主要用在 t = s + s。

总结

这题本质上不是排序所有循环串，而是在线性扫描里不断淘汰“不可能最优”的起点。

一旦想到：

把环拉直成 s + s
用最小表示法维护两个候选并整段淘汰

代码实现就比较直接了。

[SEERC 2003 / USACO5.5] 隐藏口令 Hidden Password

目录

题意

思路

代码

复杂度

总结