字典序最小循环移位

两份循环日志分别为 bbaabbaabbaa 和 aabbaabbaabb。按位置比较，它们不同；允许更换起点后，它们却是同一圈。可以把每份日志变成字典序最小的旋转，再比较规范结果。

最直接的方法要比较全部 $n$ 个长 $n$ 旋转，最坏花 $\Theta(n^2)$ 次字符工作。线性算法的关键不是更快地比较每一对，而是一次失配可以淘汰一整段起点。本页给出一个双候选实现，逐步证明淘汰规则，并处理相同字符与周期串造成的平局。

形式陈述

先明确返回什么

对非空输入 $s$ ，在它的全部循环移位中定义

a=\min\operatorname*{argmin}_{0\le k<n}\operatorname{rot}(s,k).

内层选内容最小的旋转，外层在内容相等时选最小的原始下标。本页主算法返回 $a$ ；需要规范内容时再输出 $s[a:n]s[0:a]$ ，需要全部最优起点时再用本原根长度恢复。

空输入约定返回起点零与空内容。这是方便调用的接口约定，不把零解释为空词上的模运算。算法首先处理它，后续的取模都只用于 $n\ge1$ 。

这里固定字符的全序，保留读入方向和总长度。若只想识别循环模式而忽略重复了几圈，要先取本原根；若还允许反向读取，则需要另外比较反串的规范形式。接口不同，不能在实现里静默丢掉这些信息。

双候选扫描

维护候选 $i,j$ 和已匹配长度 $k$ 。每次相等就增加 $k$ ；遇到失配，把较差候选直接跳过 $k+1$ 个位置，再把 $k$ 清零。两候选碰到同一下标时，向前再移动刚更新的那个，避免和自己比较。

python

def minimal_rotation_index(s):
    n = len(s)
    if n == 0:
        return 0
    i, j, k = 0, 1, 0
    while i < n and j < n and k < n:
        x = s[(i + k) % n]
        y = s[(j + k) % n]
        if x == y:
            k += 1
            continue
        if x > y:
            i += k + 1
            if i == j:
                i += 1
        else:
            j += k + 1
            if i == j:
                j += 1
        k = 0
    return min(i, j)

代码直接通过取模访问原串，没有创建 $ss$ 。此实现用的是双候选的失配淘汰规则；经典 Booth 算法使用修改后的 KMP 失败函数，Duval 和 Shiloach 也给出了线性方法。[1–3] 它们解决同一个问题，不应因为都叫“最小表示法”就混用不同版本的索引不变量或比较常数。

直觉

第一次失配为什么能淘汰一段

设两个候选起点为 $i,j$ 。从它们开始按环形读取，前 $k$ 个字符相等，第一处不同满足

s[(i+k)\bmod n]>s[(j+k)\bmod n].

于是起点 $i$ 输给 $j$ 。更强的是， $i,i+1,\ldots,i+k$ 中仍落在合法范围 $[0,n)$ 的每个起点，都不可能是全局最小者。

对任意 $0\le t\le k$ ，比较起点 $i+t$ 和 $(j+t)\bmod n$ 的旋转。前 $k-t$ 个字符仍相等，因为它们只是删掉了刚才共同前缀的前 $t$ 位；下一位仍是同一对失配字符，而且左边更大。所以 $i+t$ 也有一个严格更好的对手。

这个证明没有要求胜者 $j+t$ 仍保留在候选表中。只要存在一个更小旋转，就足以排除 $i+t$ 。反向失配时同理排除 $j$ 到 $j+k$ 。若比较了整整 $n$ 个字符都相等，就不存在失配，不能用严格淘汰规则删掉任何一个。

两个旋转先匹配两位再失配；将共同起点同时右移零到两格，保留同一对严格失配，因此一次排除三个起点 — 首次失配给一整段起点提供淘汰证据

停下时为什么已经有全局答案

循环保持的范围不变量是：小于 $\max(i,j)$ 的合法起点，除了仍保留的候选外，都已有严格更小的旋转作为淘汰证据。最初只有 $0,1$ 两个候选，不变量成立；每次跳跃恰由上一节证明覆盖。碰撞处理只是不再保存同一个起点的第二份副本。

若某一候选跳到 $n$ 或更远，所有其他合法起点都已被淘汰，留下的那个必为最小。若因 $k=n$ 停下，两个候选的完整旋转相等，还需解释未扫描的更大起点。

不妨此时 $i<j$ ，令 $h=j-i$ 。旋转相等说明环形串在位移 $h$ 后不变。任何起点 $r\ge j$ 都可以反复减去 $h$ ，得到一个位于 $[i,j)$ 的起点，且旋转内容不变。这个区间内除 $i$ 外的起点都已有严格淘汰证据，因此所有还没扫描的位置也不可能更好； $i$ 就是最小起点。

整个过程只严格淘汰内容更大的旋转，故不会误删一个下标更小但内容相等的最优起点。返回 $\min(i,j)$ 因而同时满足内容最小和下标最小两层要求。

例子与边界

复算一个带周期平局的例子

对 bbaabbaabbaa，从 $(i,j,k)=(0,1,0)$ 开始。起点零和一的首字符同为 b，下一位是 b>a，于是跳过起点零、一，令 $i=2$ 。与仍在一的候选比较，a<b，故 $j$ 跳到二；发生碰撞，再令 $j=3$ 。

现在比较起点二和三：第一位同为 a，第二位 a<b，起点三、四被淘汰， $j=5$ 。起点五以 b 开头，又输给起点二， $j=6$ 。

起点二和六开始的整圈都为 aabbaabbaabb，连续比较十二位全部相等， $k=n$ ，返回较小的二。程序没有继续比较到任意“看起来重复够多”的位置；完整相等的停止条件恰好是读满 $n$ 个字符。

单字符输入从一开始就有 $j=n$ ，返回零。全相等字符串如 aaaa 则在起点零、一之间匹配满四位，返回零。二者都不需要特殊的内部循环补丁，只需要入口处避免空串取模。

推论与应用

把比较次数记到淘汰的区间上

一轮失配前如果有 $k$ 次成功比较，随后失败一次，则完成了 $k+1$ 次字符对检查，同时某个候选至少前进 $k+1$ 。把这批比较收费给该候选本次跳过的索引，便不会跨轮重复收费。

$i,j$ 都只增加。一个候选在最后一次跳跃中可能超过 $n$ ，但跳跃长度至多为 $n$ ，故两个索引的总增量仍是 $O(n)$ 。此外，若最后一轮匹配满 $n$ 位，再单独加 $n$ 次检查即可。因此总时间为 $O(n)$ ，工作空间为常数个机器字。

返回起点不需要复制字符串；真正输出长 $n$ 的规范表示要另外花 $\Theta(n)$ 时间与字符空间。每个下标和长度需要 $O(\log(n+1))$ bits，常数工作空间指的是常数个能容纳这些数的机器字，并非与 $n$ 无关的固定比特数。

全部最优起点与本原代表

设输入的本原根长度为 $d$ ，已经求得最小起点 $a$ 。旋转计数定理说明全部最优起点恰为

a,a+d,a+2d,\ldots<n.

由于 $a$ 是最小起点，必有 $0\le a<d$ ；否则 $a-d$ 就是一个更早的相同旋转。先用前缀函数求根长 $d$ ，再按间隔输出，总时间仍为 $O(n)$ ，其中输出本身需 $\Theta(n/d)$ 项。这个配套方法额外使用前缀函数的 $O(n)$ 存储；不要把主算法的常数工作空间直接套到整套接口上。

例子中 $d=4,a=2$ ，全部最优起点为 $2,6,10$ 。取规范串的前四个字符 aabb，它是本原根循环类的唯一Lyndon 代表；规范整串则是 $(\texttt{aabb})^3$ ，自身不是 Lyndon 词。于是本原根、Lyndon 代表和一般循环串规范化在这里接上了。

单元终结任务：给循环日志交付一份可核验结果

给定 $s=\texttt{bbaabbaabbaa}$ ，字母序为 $a<b$ 。不要只交一个字符串，完成以下五项：

写出前缀函数末值、最短周期、本原根和指数
给出 CFL 分解的全部半开区间，并解释为何每块合法且非增
手算 Duval 的三个输出批次，说明第二轮为何留下 aa
求最小旋转、最小起点和全部并列起点，给出每次失配淘汰的范围
比较 aabbaabb 与 $s$ ：若保留整圈长度，它们是否相同；若只比较本原循环模式，结论是否改变

核对结果：末值八，最短周期四，根 bbaa，指数三；CFL 区间为 $[0,1),[1,2),[2,6),[6,10),[10,11),[11,12)$ ；最小内容为 aabbaabbaabb，最小起点二，全部起点 $\{2,6,10\}$ 。长度八的 aabbaabb 不与长度十二的 $s$ 共轭，但二者本原根的最小旋转同为 aabb，因此在“忽略圈数”的另一个接口下相同。

最后加一个拒绝测试：长度六的 abaaba 虽有周期三和五，不能合并成周期一，因为 $6<3+5-1$ 。这项检查防止把“重复模式规范化”错误实现成“不管长度门槛，直接对周期取 gcd”。

配套的可执行核验脚本枚举短词，将线性算法与独立暴力定义对照，同时核验周期、本原根、CFL 唯一切分、全部旋转起点和空串接口。小规模穷举能抓住索引错误，正确性的普遍保证仍来自上面的不变量与淘汰证明。

参考资料

[1] K. S. Booth, “Lexicographically Least Circular Substrings”, Information Processing Letters 10(4–5), 1980, pp. 240–242，DOI：修改失败函数的经典线性算法。
[2] Yossi Shiloach, “Fast Canonization of Circular Strings”, Journal of Algorithms 2(2), 1981, pp. 107–121：全部最小起点、周期间隔与常数辅助存储；该文的更优比较常数不是本文双候选实现的保证。
[3] Jean-Pierre Duval, “Factorizing Words over an Ordered Alphabet”, Journal of Algorithms 4(4), 1983, pp. 363–381：Lyndon 分解及最小循环移位应用。

形式陈述 ​

先明确返回什么 ​

双候选扫描 ​

第一次失配为什么能淘汰一段 ​

停下时为什么已经有全局答案 ​

复算一个带周期平局的例子 ​

把比较次数记到淘汰的区间上 ​

全部最优起点与本原代表 ​

单元终结任务：给循环日志交付一份可核验结果 ​

反向链接