词的共轭与循环移位

两倍串为什么包含所有旋转 ​

写出 $ss$。对每个 $0\le k<n$，长度为 $n$ 的窗口

正好是从 $s[k]$ 读到串尾，再从串首读到 $s[k-1]$，也就是 $\mathrm{rot}(s,k)$。反过来，任何起点小于 $n$ 的这种窗口都对应一个合法切口。

因此等长非空词 $s,t$ 共轭，当且仅当 $t$ 出现在 $ss$ 的某个起点 $k<n$。要避免起点 $n$ 重复报告零起点，可以只搜索长度 $2n-1$ 的文本 $ss[0:2n-1]$。使用KMP理路KMP 算法Knuth–Morris–Pratt algorithm利用模式自身前后缀信息避免文本指针回退的线性时间字符串匹配算法。找一个出现或全部出现，预处理与扫描都是 $O(n)$；模式的失败数组占 $O(n)$ 个整数单元。

不一定要真正复制 $ss$。向匹配器提供第 $i$ 个字符 $s[imodn]$，依次供给 $2n-1$ 个字符即可。这样省去双倍文本副本，但不减少读取次数，也不自动消除 KMP 的模式数组空间。

长度不同必须先拒绝。即使 ab 出现在 abababab 中，它也不是 abab 的旋转，因为绕完一圈的长度不同。若应用希望忽略重复圈数，应先比较本原根理路本原词与唯一重复根Primitive word · Primitive root of a word · 本原字 · 字符串本原根不能写成更短非空词的二次或更高整数幂的词称为本原词；每个非空词都能唯一写成本原根的正整数幂。的循环表示，那是另一个明确不同的接口。

与后缀、反转的区别 ​

有限后缀 $s[k:n]$ 走到串尾就停止，旋转则继续从头读取，直到恰好读完 $n$ 个字符。例如 baab 的最小非空后缀是 aab，从同一起点一开始确实也得到最小旋转 aabb，但这只是一例巧合。baa 的最小后缀是最后一个 a，该起点的旋转是 aba；真正最小旋转是从前一个 a 开始的 aab。

因此不能把后缀数组理路后缀数组Suffix array按字典序排列字符串全部后缀起始位置的数组索引。的第一项直接当成最小旋转起点。BWT理路Burrows–Wheeler 变换Burrows-Wheeler transform · BWT对带唯一终止符文本的循环移位排序，并取最后一列形成可逆排列。把全部循环移位排序，接入唯一最小终止符后可以和后缀排序对应；这里的终止符承担了固定边界的作用，不能擅自删去这个条件。

本页的旋转不允许倒着读。abc 的旋转只有 abc,bca,cab，不包含 acb。项链若允许翻面，或者几何轮廓若不区分顺逆方向，还要额外把反转纳入等价关系；直接使用本页的共轭检查会保留方向信息，这通常正是日志所需要的。

手算终点 ​

检查 aabb 是否与 bbaa 共轭：在 bbaabbaa 中找到长四窗口，起点二给出 aabb，证据是切分 bb|aa 变成 aa|bb。

再检查 abab 与 aabb。两者长度相同、字符计数相同，却没有任何合法窗口相等。abababab 的长四窗口只能是 abab 或 baba，因此拒绝。最后解释为什么 abab 的本原根长二，正好与两种不同窗口内容一致。

这些证据都是可以独立检查的：接受时给起点和一次切分；拒绝时可以给出完整匹配扫描的结果。接下来，Lyndon 词理路Lyndon 词Lyndon word · Lyndon字 · 林登词在固定字母序下严格小于每个非零循环移位的非空词，等价于严格小于每个非空真后缀的词。会在本原共轭类中选一个唯一的最小代表，最小旋转算法理路字典序最小循环移位Lexicographically minimal string rotation · Least circular shift · Minimal rotation · 最小表示法通过首次失配一次排除一段旋转起点，在线性时间求循环串的字典序最小表示，并以本原根周期恢复全部并列起点。则处理包括非本原词在内的一般输入。

有 n 个起点，未必有 n 种表示 ​

abab 的四次旋转是 abab,baba,abab,baba。不同起点得到相同内容，来自原串本身的重复。

设 $s=r^m$，$r$ 是本原根，$d=|r|$，所以 $n=md$。那么：

• 不同旋转恰有 $d$ 种
• 每种旋转恰由 $m$ 个起点产生
• 两个起点 $i,j$ 给出同一旋转，当且仅当 $i\equiv j(\mathrm{mod}d)$

充分性直观：每走 $d$ 个字符就是越过一整份重复块，读到的整圈没有变化。必要性需要排除另一种隐藏重复。

如果位移 $k$ 保持整串不变，那么所有位置满足 $s[i]=s[(i+k)modn]$。在模 $n$ 的位置上反复加 $k$，一个轨道恰好覆盖某个模 $g=gcd(n,k)$ 的余数类，这里的 $g$ 是最大公约数理路最大公约数Greatest common divisor · GCD同时整除两个整数且被所有公约数整除的非负整数。。因此同一模 $g$ 类里的字符全相等，$s$ 是长 $g$ 前缀的 $n/g$ 次幂。

唯一根定理说明 $d\mid g$，进而 $d\mid k$。对于一般的两个起点，先撤销其中一个位移，就回到刚证明的情形。由此得到准确的起点等价规则。

在 bbaabbaabbaa 中，本原根长四，所以只有四种不同旋转，每种由三个起点给出。最小内容 aabbaabbaabb 出现在 $2,6,10$，它们都同余于二模四。原始起点数十二、不同内容数四、每个内容的重数三，是三个不能混为一谈的计数。