1. 定义

一个字符串 \(S\) 被定义为 Lyndon Word 当且仅当其严格小于所有真 cyclic shift。

Lyndon Word 的等价定义：是其所有后缀中最小的。

2. 性质

性质 1： Lyndon Word 无 \(\text{Border}\)。

不妨设 \(w\) 有 \(\text{Border}\)，则我们可以表示为 \(w = xu = uy\)，从而得到 \(w < ux, w < uy\)，替换一下得到 \(y < x\) 和 \(x < y\)，显然矛盾。

性质 2： \(u, v\) 都是 Lyndon Word，则 \(uv\) 是 Lyndon Word \(\iff u < v\)。

如果 \(uv\) 是 Lyndon Word，则我们得到 \(uv < v\)，同时 \(u < uv\)，所以 \(u < v\)。

我们分情况考虑三种后缀。

第一种，\(s = u'v\)我们知道 \(u < u'\)，因为 \(|u| > |u'|\)，所以加上 \(v\) 依然成立。

第二种 \(v\)，我们考虑证明 \(uv < v\)，按照长度来，如果 \(u > v\) 显然成立，否则若 \(u\) 为 \(v\) 的前缀，不妨设 \(v = uv'\)，我们已知 \(v < v'\)，所以 \(uv < uv'\) 得证。

第三种比 \(v\) 还小的可以从第二种直接看出来。

性质 3： \(w\) 是 Lyndon Word \(\iff \forall w = uv\)，\(u < v\)（\(u, v\) 非空）

从左边往右，我们知道 \(uv < v\) 和 \(u < uv\) 即可推出。

反过来，我们需要证明 \(uv < vu\)，这是根据定义来证明，分两种情况。

我们设 \(a<_!b\) 表示 \(a\) 小于 \(b\) 且不是 \(b\) 的前缀。

如果 \(u<_!v\)，则不难推出 \(uv < vu\)。否则，我们设 \(v = u^kr\)，其中 \(u\) 不是 \(r\) 的前缀。

由于 \(w = uv = u^{k+1}r\)，得到 \(u^{k+1} < r\) 从而 \(u < r\)，于是 \(u <_! r\) 最终得到 \(ur < ru\)。

所以我们有 \(uv = u^{k} u r > u^{k}ru = vu\)，得证。

性质 4（标准分解）： \(w\) 是 Lyndon Word，取最小真后缀 \(v\)，假设 \(w = uv\)，则：\(u,v\) 也是 Lyndon Word 且 \(u < v\)，并且 \(v\) 是 \(w\) 的最长 Lyndon Word 真后缀。

由于 \(v\) 是最小真后缀，所以显然 \(v\) 是 Lyndon Word，而 \(u\) 的所有后缀 \(u'\) 均满足 \(uv < u'v\)，由于 \(|u| > |u'|\)，说明 \(u\) 一定小于 \(u'\)。

递归定义： \(w\) 是 Lyndon Word 当且仅当 \(|w| = 1\) 或存在 \(w = uv, u < v\) 且 \(u, v\) 是 Lyndon Word。

递归定义是性质 4 的推论。