Lyndon 分解

定义

首先我们介绍 Lyndon 分解的概念。

Lyndon 串：对于字符串 $s$ ，如果 $s$ 的字典序严格小于 $s$ 的所有后缀的字典序，我们称 $s$ 是简单串，或者 Lyndon 串。举一些例子，a,b,ab,aab,abb,ababb,abcd 都是 Lyndon 串。当且仅当 $s$ 的字典序严格小于它的所有非平凡的（非平凡：非空且不同于自身）循环同构串时， $s$ 才是 Lyndon 串。

Lyndon 分解：串 $s$ 的 Lyndon 分解记为 $s = w_{1} w_{2} \dots w_{k}$ ，其中所有 $w_{i}$ 为简单串，并且他们的字典序按照非严格单减排序，即 $w_{1} \geq w_{2} \geq \dots \geq w_{k}$ 。可以发现，这样的分解存在且唯一。

Duval 算法

解释

Duval 可以在 $O (n)$ 的时间内求出一个串的 Lyndon 分解。

首先我们介绍另外一个概念：如果一个字符串 $t$ 能够分解为 $t = w w \dots \overset{―}{w}$ 的形式，其中 $w$ 是一个 Lyndon 串，而 $\overset{―}{w}$ 是 $w$ 的前缀（ $\overset{―}{w}$ 可能是空串），那么称 $t$ 是近似简单串（pre-simple），或者近似 Lyndon 串。一个 Lyndon 串也是近似 Lyndon 串。

Duval 算法运用了贪心的思想。算法过程中我们把串 $s$ 分成三个部分 $s = s_{1} s_{2} s_{3}$ ，其中 $s_{1}$ 是一个 Lyndon 串，它的 Lyndon 分解已经记录； $s_{2}$ 是一个近似 Lyndon 串； $s_{3}$ 是未处理的部分。

过程

整体描述一下，该算法每一次尝试将 $s_{3}$ 的首字符添加到 $s_{2}$ 的末尾。如果 $s_{2}$ 不再是近似 Lyndon 串，那么我们就可以将 $s_{2}$ 截出一部分前缀（即 Lyndon 分解）接在 $s_{1}$ 末尾。

我们来更详细地解释一下算法的过程。定义一个指针 $i$ 指向 $s_{2}$ 的首字符，则 $i$ 从 $1$ 遍历到 $n$ （字符串长度）。在循环的过程中我们定义另一个指针 $j$ 指向 $s_{3}$ 的首字符，指针 $k$ 指向 $s_{2}$ 中我们当前考虑的字符（意义是 $j$ 在 $s_{2}$ 的上一个循环节中对应的字符）。我们的目标是将 $s [j]$ 添加到 $s_{2}$ 的末尾，这就需要将 $s [j]$ 与 $s [k]$ 做比较：

如果 $s [j] = s [k]$ ，则将 $s [j]$ 添加到 $s_{2}$ 末尾不会影响它的近似简单性。于是我们只需要让指针 $j, k$ 自增（移向下一位）即可。
如果 $s [j] > s [k]$ ，那么 $s_{2} s [j]$ 就变成了一个 Lyndon 串，于是我们将指针 $j$ 自增，而让 $k$ 指向 $s_{2}$ 的首字符，这样 $s_{2}$ 就变成了一个循环次数为 1 的新 Lyndon 串了。
如果 $s[j]

本页面最近更新：2024/2/15 22:17:29，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：iamtwz, orzAtalod, sshwy, StudyingFather, ksyx, Xeonacid, Chrogeek, diauweb, Enter-tainer, gi-b716, hqztrue, Junyan721113, Menci, shawlleyw, Soresen, Suyun514
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用