Lyndon 词

为什么每个本原循环类恰有一个 ​

如果 $w=u^m$、$m\ge 2$，移动 $|u|$ 个位置不改变内容，严格不等式失败。因此 Lyndon 词必是本原词理路本原词与唯一重复根Primitive word · Primitive root of a word · 本原字 · 字符串本原根不能写成更短非空词的二次或更高整数幂的词称为本原词；每个非空词都能唯一写成本原根的正整数幂。。

反过来，一个本原词的全部 $n$ 个旋转都不同，这已由旋转的计数规则理路词的共轭与循环移位Conjugate words · Cyclic rotation of a word · Circular string · 词的旋转等价把词切为 uv 再连接成 vu 定义旋转等价；本原根的长度决定不同旋转的个数和相同旋转起点的间隔。证明。有限个互异词在全序中恰有一个最小者；它严格小于其余旋转，所以是 Lyndon 词。

因此“本原”与“类中最小”合在一起才等价于 Lyndon 条件。非本原循环类仍然有最小的内容，但多个切口得到该内容，不能满足严格比较。这一细节在随后最小旋转算法的并列输出中会重新出现。

不绕圈也能判定：与全部真后缀比较 ​

一个非空词 $w$ 是 Lyndon 词，当且仅当

例如 aabb 的真后缀为 abb,bb,b。和 abb 比较时，首位同为 a，第二位 a<b；另外两个后缀都以 b 开头。三次比较全部通过，不必真的拼接循环移位。

先证明后缀条件足够。写 $w=uv$，其中 $u,v$ 非空。既然 $w<v$，决定大小的差异必发生在 $v$ 结束之前：$w$ 更长，不可能是 $v$ 的真前缀，而若 $v$ 是 $w$ 的前缀又会有 $v<w$。旋转 $vu$ 以 $v$ 开始，保留这个决定性差异，所以 $w<vu$。

再证明必要性，需要先排除 border。假设一个严格最小旋转 $w$ 有非空真 border $v$，则同时可写成

由在切口 $|u|$ 处的严格最小性，有 $vz=w<vu$，消去共同前缀 $v$ 得 $z<u$。因为 $z,u$ 等长，后面各接 $v$ 不会改变这个严格比较，于是 $zv<uv=w$。但 $zv$ 也是 $w=vz$ 的一个旋转，矛盾。所以 Lyndon 词无非空真 border。

现在取任意非空真后缀 $v$。它不可能同时是前缀；比较 $w$ 和 $v$ 必在 $v$ 结束前出现字符差异。如果该差异给出 $v<w$，旋转 $vu$ 也会小于 $w$，再次矛盾。因此只能有 $w<v$。两向证明完成。

这个判据也解释了 aba 为什么失败：真后缀 a 是它的真前缀，所以 a<aba。无 border 是必要条件，却仍不是充分条件；ba 无非空 border，但真后缀 a 更小。

如何检查一张小证书 ​

对于教学实例，直接比较每个真后缀即可。最多 $n-1$ 次比较，每次最多查看 $n$ 个字符，因此最坏 $O(n^2)$。只存切片边界可用常数个索引；若语言的切片会复制，需把临时复制成本和空间计入。不能说“比较了 $n$ 个后缀”就算成 $O(n)$ 时间。

Duval 算法理路Duval 线性 Lyndon 分解算法Duval's algorithm · Duval factorization · Duval算法用三个索引维护 Lyndon 块的重复前缀，遇到较小字符或串尾就批量输出完整块，在 O(n) 时间和常数工作空间内生成 CFL 分解。能在线性时间把任意词分成非增的 Lyndon 因子。若分解只有一个因子且它就是整串，那么整串是 Lyndon 词。这是一种高效识别途径，依据的是下一页唯一分解定理；定义本身并不要求先运行它。

字母序必须在整个任务中固定。若把 a<b 改为 b<a，aabb 不再是本原循环类的最小代表。大小写折叠、Unicode 规范化和语言排序规则属于输入解释，不能在算法中途更换比较器。这里的字符可以是编号事件，只要比较确定且形成全序即可。

手算终点 ​

判断 aab、aba、baa。三者同属一个本原循环类，最小的 aab 是唯一 Lyndon 代表；它小于真后缀 ab,b。另外两个分别被真后缀 a 和 aa 否定。

再判断 aabaabab。可以先尝试切成 aab|aabab：两块都是 Lyndon 词且前者小于后者，所以连接规则直接给出肯定答案，不必逐一列出七个旋转。这个方法展示了结构性证据如何代替重复比较。下一页将反过来把任意字符串拆成有唯一顺序的 Lyndon 块。

两个递增 Lyndon 块可以接成一个 ​

下面这个连接规则是下一页分解定理的关键：若 $u,v$ 都是 Lyndon 词，并且 $u<v$，那么 $uv$ 也是 Lyndon 词。[1]

先证明 $uv<v$。若 $u,v$ 在较短者结束前已有差异，$u<v$ 的决定性字符在连接后仍存在。剩下的情形是 $u$ 为 $v$ 的真前缀，写 $v=uz$。由于 $v$ 是 Lyndon 词，有 $v<z$，两侧接上相同前缀 $u$ 得 $uv<uz=v$。

再检查 $uv$ 的所有非空真后缀。完全位于 $v$ 内的后缀 $t$ 满足 $v\le t$，所以 $uv<v\le t$。从 $u$ 内部开始的后缀形如 $tv$，其中 $t$ 是 $u$ 的非空真后缀；$u<t$ 的决定性字符在 $t$ 结束前出现，因此接上后续内容仍有 $uv<tv$。所有后缀都通过判据，故 $uv$ 是 Lyndon 词。

取 $u=\mathtt{\text{ab}},v=\mathtt{\text{abb}}$，有 $u<v$，于是 ababb 是 Lyndon 词。如果把两个块颠倒成 abbab，结论不再适用，它确有更小后缀 ab。如果取相等块 ab,ab，连接成 abab 也不是 Lyndon 词。因此这里必须是严格递增，不能把 $<$ 改成 $\le$。