最小表示法

“循环同构 (Cyclic Shift)”

一个字符串 S 的所有循环同构串，是指通过将 S 的前 k 个字符（0 <= k < n，n 为字符串长度）依次移动到字符串末尾而得到的所有字符串的集合。

例如，字符串 s = "abc" 的循环同构串有三个：

• "abc" (k=0)
• "bca" (k=1)
• "cab" (k=2)

最小表示法 (Minimal Representation) 的任务就是，从一个字符串的所有循环同构串中，找出字典序最小的一个。我们通常返回其在原字符串中的起始下标。

关键思路

暴力解法

最直观的思路是枚举所有可能的起始位置（从 0 到 n-1），生成对应的循环同构串，然后两两比较，找出字典序最小的那个。

这种方法需要两层循环：外层循环枚举挑战者，内层循环进行字符串比较。在最坏情况下（例如字符串为 aaaa...aab），每次比较都需要接近 n 次操作，总时间复杂度会退化到 $O(n^2)$。

优化思路：双指针法

暴力解法的瓶颈在于做了大量冗余的比较。很多字符串在比较的初期就已经“败下阵来”，但我们没有有效利用这个信息。

优化的核心思想类似于 KMP 算法：当比较出现不一致时，利用已知信息，尽可能多地排除不可能是答案的候选位置。

我们使用两个指针 i 和 j，分别指向两个候选的起始位置。k 用来记录 s[i...] 和 s[j...] 两个子串匹配的长度。

1. 初始化：i = 0, j = 1, k = 0。
2. 比较：比较 s[(i+k)%n] 和 s[(j+k)%n]。
   • 相等：如果字符相同，说明 i 和 j 开头的字符串在前 k+1 个字符上仍然是“势均力敌”的。我们增加 k，继续向后比较。
   • 不相等：假设 s[(i+k)%n] > s[(j+k)%n]，这意味着以 i 开头的字符串在前 k 个字符与 j 相同，但在第 k 个字符处字典序更大。因此，i 所代表的字符串“落败”。
     • 此时，不仅 i 被排除了，所有以 i 到 i+k 开头的字符串都可以被排除。因为对于任何 0 <= p <= k，s[j+p] 都等于 s[i+p]，而 s[j+p] 对应的候选串 s[j...] 已经证明比 s[i...] 更优，所以 s[i+p...] 也没有机会。
     • 因此，我们可以安全地将 i 指针移动到 i+k+1 的位置，然后从头开始比较（k=0）。
   • 同理，如果 s[(i+k)%n] < s[(j+k)%n]，则 j 落败，我们将 j 移动到 j+k+1。

为了避免 i 和 j 指向同一个位置，如果 i 在更新后等于 j，则让 i（或j）再前进一位。

这个过程不断进行，i 和 j 像两名选手在比赛，输的一方会大幅前进，跳过大量不可能的位置。当其中一个指针超过 n 时，比赛结束，未出局的指针就是最小表示的起始位置。

算法步骤

1. 初始化指针 i = 0, j = 1, k = 0。
2. 当 i < n, j < n, k < n 时，循环执行以下步骤： a. 计算当前要比较的字符：char_i = s[(i + k) % n] 和 char_j = s[(j + k) % n]。 b. 如果 char_i == char_j，则 k 自增 1，继续比较下一个字符。 c. 如果 char_i > char_j，说明以 i 开头的字符串不是最优的。将 i 更新为 i + k + 1。 d. 如果 char_i < char_j，说明以 j 开头的字符串不是最优的。将 j 更新为 j + k + 1。 e. 在 c 或 d 之后，重置 k = 0。 f. 如果更新后 i == j，则将 j 自增 1。
3. 循环结束后，min(i, j) 即为最小表示的起始下标。

算法证明

该算法的关键在于一次失配可以排除 k+1 个候选位置的正确性。

假设在比较 s[i...] 和 s[j...] 时，它们的前 k 个字符相同，即 s[i..i+k-1] == s[j..j+k-1]，但在第 k 个字符处 s[i+k] > s[j+k]。

这意味着字符串 s[i...] 比 s[j...] 要差。

现在我们考虑任何一个在 [i, i+k] 区间内的起始位置 i+p（0 <= p <= k）。对应的竞争者是 s[j+p...]。由于 s[i..i+k-1] == s[j..j+k-1]，我们有 s[i+p..i+k-1] == s[j+p..j+k-1]。 而 s[i+k] > s[j+k]。 这意味着 s[i+p...] 和 s[j+p...] 的第一个不同点，就是 s[i+k] 和 s[j+k] 的比较，且前者更大。所以 s[j+p...] 总是优于 s[i+p...]。

因此，i 到 i+k 之间的所有位置都不可能是最小表示的起点，我们可以安全地将 i 移动到 i+k+1。

复杂度分析

• 时间复杂度: $O(n)$。虽然代码看起来有多重循环，但我们可以分析指针移动的总次数。i 和 j 两个指针都只会单调递增。在每次比较中，要么 k 增加，要么 i 或 j 中的一个增加 k+1。i+j+k 的值在每次迭代中都是增加的，其最大值不超过 3n。因此，总的比较次数是线性的。
• 空间复杂度: $O(1)$。我们只使用了常数个额外变量。

代码实现

下面是根据上述思想实现的C++代码。

测试用例

让我们用字符串 s = "abacaba" (n=7) 来手动模拟算法。

1. 初始: i = 0 (abacaba), j = 1 (bacabaa), k = 0。
2. s[0] (‘a’) < s[1] (‘b’)。j 落败。j = j + k + 1 = 1 + 0 + 1 = 2。k = 0。
   • i = 0 (abacaba), j = 2 (acabaab)。
3. s[0] (‘a’) == s[2] (‘a’)。k = 1。
4. s[1] (‘b’) < s[3] (‘c’)。j 落败。j = j + k + 1 = 2 + 1 + 1 = 4。k = 0。
   • i = 0 (abacaba), j = 4 (abaabca)。
5. s[0..2] (aba) == s[4..6] (aba)。k 增加到 3。
6. s[3] (‘c’) > s[(4+3)%7=0] (‘a’)。i 落败。i = i + k + 1 = 0 + 3 + 1 = 4。k = 0。
   • i = 4 (abaabca), j = 4。
7. i == j，j 变为 5。
   • i = 4 (abaabca), j = 5 (baabaca)。
8. s[4] (‘a’) < s[5] (‘b’)。j 落败。j = j + k + 1 = 5 + 0 + 1 = 6。k = 0。
   • i = 4 (abaabca), j = 6 (aabacab)。
9. s[4] (‘a’) == s[6] (‘a’)。k = 1。
10. s[5] (‘b’) > s[(6+1)%7=0] (‘a’)。i 落败。i = i + k + 1 = 4 + 1 + 1 = 6。k = 0。
    • i = 6 (aabacab), j = 6。
11. i == j，j 变为 7。
12. j 到达 n，循环结束。

最终 min(i, j) = min(6, 7) = 6。 所以，最小表示是从下标 6 开始的字符串 aabacab。

实践思考与扩展

• 非循环字符串: 这种双指针竞争的思想也可以用于非循环字符串的问题。例如，LeetCode 1044. 最长重复子串 和 LeetCode 1163. 按字典序排在最后的子串 都可以借鉴类似的思想来优化。
• 多个最小表示: 如果一个字符串有多个相同的最小表示（例如 s = "ababab"），该算法会返回这些表示中的第一个。

参考

• OI Wiki - 最小表示法