Lyndon Word and The Runs Theorem

最近回去啃了啃WC的另一份课件，算是为自己两年前的作品写下续章吧。

本文是yjz、xyx、csl三人在WC2019营员交流课件的笔记。

符号和约定

为了方便本文的叙述，采用如下可能不严谨的定义：我们记 $w [i : j]$ 表示 $w$ 从第 $i$ 个字符到第 $j$ 个字符组成的子串，当 $i = 1$ 或 $j = | w |$ 时， $i$ 或 $j$ 可以省略， $i = j$ 时，可以简记为 $w [i]$ 。对于字符串 $u, v$ ，记 $u ⊲ v$ ，如果 $u < v$ 且 $u$ 并非 $v$ 的前缀，即两者在结束之前就比较出了大小。一个比较显然的结论是，如果 $u ⊲ v$ ，那么对任意字符串 $w_{1}, w_{2}$ ，有 $w_{1} u ⊲ w_{1} v$ 且 $u w_{1} ⊲ v w_{2}$ 。

定义1

如果字符串 $w$ 满足对于 $i = 2, 3, \dots, | w |$ ，都有 $w < w [i :]$ ，那么称 $w$ 是一个Lyndon串，即 $w$ 的任意严格后缀都大于 $w$ 本身。

定理1

如果 $u, v$ 都是Lyndon串，且 $u < v$ ，那么 $u v$ 是Lyndon串。

证明：将 $u v$ 的后缀 $(u v) [i :]$ 分为三部分： $i \in [2, | u |], i = | u | + 1, i \in [| u | + 2, | u v |]$ 。对于第一部分，考虑 $u$ 是一个Lyndon串，对于其严格后缀 $u [i :]$ ，有 $u ⊲ u [i :]$ ，从而有 $u v ⊲ (u v) [i :]$ 。对于第二部分，若 $u ⊲ v$ ，则显然 $u v ⊲ (u v) [| u | + 1 :]$ ；否则 $u$ 是 $v$ 的前缀，有 $[u v < v] \Leftrightarrow [v < v [| u | + 1 :]]$ ，由 $v$ 是Lyndon串，立得后者成立。对于第三部分，考虑 $u v < v < v [i - | u | :] = (u v) [i :], i \in [| u | + 2, | u v |]$ 即可。

定理2

如果 $u$ 是Lyndon串，设 $a$ 为一个字符，那么对于字符串 $u^{k} u [: i - 1] a, i \in [1, | u |]$ ，有： 1.若 $a < u [i]$ ，那么 $u$ 是任意以 $u^{k} u [: i - 1] a$ 开头的字符串的最长Lyndon前缀。 2.若 $a > u [i]$ ，那么 $u^{k} u [: i - 1] a$ 是Lyndon串。

证明：对 $a < u [i]$ 的情况，由于 $u^{n} u [: i]$ 若并非 $u$ 本身，就是周期串，不可能是Lyndon串。对于剩下的更长的前缀，不妨假设其为 $u^{k} u [: i - 1] a v$ ，从而有 $u [: i - 1] a v$ 作为后缀，由于 $u [: i - 1] a ⊲ u$ ，因此 $u [: i - 1] a v ⊲ u^{k} u [: i - 1] a v$ ，从而 $u^{k} u [: i - 1] a v$ 不可能是Lyndon串。第一部分得证。对 $a > u [i]$ 的情况，将 $u^{k} u [: i - 1] a$ 的严格后缀分为以 $u$ 开头的、以 $u$ 的严格后缀 $u [i :]$ 开头的和 $a$ 。对于以 $u$ 开头的，假设其为 $u^{k^{'}} u [: i - 1] a (k^{'} < k)$ ，由 $u ⊲ u [: i - 1] a$ ，立得 $u^{k^{'} + 1} ⊲ u^{k^{'}} u [: i - 1] a$ ，从而 $u^{k} u [: i - 1] a < u^{k^{'}} u [: i - 1] a$ ；对于以 $u [i :]$ 开头的，由 $u [i :] ⊲ u$ 立得其小于 $u^{k} u [: i - 1] a$ ；最后，由 $u \leq u [i] < a$ ，即得 $a$ 也大于整个串。因此， $u^{k} u [: i - 1] a$ 是Lyndon串。

定义2

对于字符串 $w$ ，若存在一组Lyndon串 $u_{1}, u_{2}, \dots, u_{n}$ ，满足 $w = u_{1} u_{2} \dots u_{n}$ 且 $u_{1} \geq u_{2} \geq \dots \geq u_{n}$ ，那么称 $u_{1}, u_{2}, \dots, u_{n}$ 为 $w$ 的Lyndon分解。

定理3

任意字符串 $w$ 的Lyndon分解存在。

证明：采用构造法并对 $w$ 的后缀归纳证明。设 $u_{1}^{'}, u_{2}^{'}, \dots, u_{m}^{'}$ 是 $w [2 :]$ 的一组Lyndon分解，由于 $w [1]$ 是Lyndon串，有 $w = w [1] u_{1}^{'} u_{2}^{'} \dots u_{m}^{'}$ ，对于这组“初步的”Lyndon分解，由定理1，只要开头的两个Lyndon串是小于关系，就合并为一个新Lyndon串，反复操作直到只剩下一个串或者是不小于的关系，就得到了 $w$ 的一组Lyndon分解。

定理4

任意字符串 $w$ 的Lyndon分解唯一。

证明：只要证明 $w$ 的任意Lyndon分解的第一个字符串 $w [: i]$ 一定是 $w$ 的最长Lyndon前缀，之后考虑余下的串是 $w [i + 1 :]$ 的Lyndon分解，归纳证明即可。反证法，假设存在更长的Lyndon前缀 $w [: j] (i < j)$ ，则该Lyndon分解 $w [: i] u_{2} u_{3} \dots u_{n}$ 中，存在一个 $u_{k}$ 满足其是第一个右端点位置 $\geq j$ 的串，不妨记为 $w [i^{'} : j^{'}]$ ，考虑 $w [: j]$ 是Lyndon串，因此 $w [: i] < w [: j] < w [i^{'} : j] \leq w [i^{'} : j^{'}] = u_{k}$ ，得到 $w [: i] < u_{k}$ ，与Lyndon分解是不递增的矛盾。综上所述Lyndon分解唯一。

初步的Lyndon分解算法

在定理4保证了Lyndon分解的唯一性后，定理3实际上给出了一个求Lyndon分解的算法。通过哈希或后缀数组预处理后判断子串的大小关系，并沿用定理3证明中的过程，就可以做到 $O (n \log n)$ 求解Lyndon分解。当然，采用 $SA-IS$ 和 $O (n) - O (1) RMQ$ 可以使算法做到 $O (n)$ ，然而这样的实现并不实用。

高效的Lyndon分解算法

通过定理2给我们的启发，有可能找到更好的Lyndon分解算法。考虑将 $w$ 划分为三部分，记录 $i, k, p$ 表示 $w [: i]$ 已经进行了Lyndon分解，并确定必定是 $w$ 的Lyndon分解的前若干项，而 $w [i + 1 : k]$ 则是一个形如 $u^{k} u [: j - 1]$ 的串，其中 $u$ 是Lyndon串且长度为 $p$ ， $w [k + 1 :]$ 则是未知情况的串。考虑不断进行如下迭代，直到 $i$ 变为 $| w |$ ：考察 $w [k + 1]$ （若 $k + 1 > | w |$ ，则定义 $w [k + 1]$ 是小于任何字符集中字符的特殊字符 $$$ ），分三类情况： 1. $w [k + 1] = w [k + 1 - p]$ ，则 $u^{k} u [: j - 1]$ 的形式继续保持，令 $k$ 自增 $1$ 即可。 2. $w [k + 1] > w [k + 1 - p]$ ，则由定理 $2$ 可知， $w [i + 1, k + 1]$ 是一个Lyndon串，但是不能保证其一定出现在最终的Lyndon分解中。不过，这仍满足 $u^{k} u [: j - 1]$ 的形式（ $k = j = 1$ ），于是令 $k$ 自增 $1$ ，而 $p$ 为 $k - i + 1$ 即可。 3. $w [k + 1] < w [k + 1 - p]$ ，则由定理 $2$ 可知， $u$ 必定是 $w [i + 1 :]$ 的最长Lyndon前缀。由定理4可知，其一定出现在Lyndon分解中，于是我们将 $k$ 个 $u$ 全部加入已知的Lyndon分解中。对于剩下的 $u [: j - 1]$ ，无法保证其满足 $u^{' k} u^{'} [: j - 1]$ 的形式，干脆重新开始，令 $k$ 指向 $u [: j - 1]$ 的第一个字符（单字符必定是Lyndon串），并令 $i = k - 1, p = 1$ 。

综上即得Lyndon分解，每次迭代是 $O (1)$ 的，且 $i + k$ 至少增加 $1$ 。由于 $i, k \leq | w |$ ，因此整个算法是 $O (n)$ 的，并且有非常简洁的实现。

The Runs Theorem 部分待填坑。