Lyndon 分解(Duval 算法)

Lyndon 分解是字符串理论中的一个基本定理:任意非空字符串都可以唯一地分解为若干个 Lyndon 串的连接,且这些 Lyndon 串按字典序非递增排列。Duval 算法则是求解这一分解的经典线性算法。

概述

所谓 Lyndon 串,是指严格小于自身所有真后缀(等价地,严格小于其所有循环移位)的字符串。Lyndon 分解定理保证这种分解存在且唯一,记作字符串等于 w1 w2 … wk,其中每个 wi 是 Lyndon 串且字典序满足 w1 大于等于 w2 大于等于 … 大于等于 wk。Duval 算法由 Jean-Pierre Duval 于 1983 年提出,可在线性时间内完成分解。

核心原理

Duval 算法维护三个指针,通过比较字符逐步确定每个 Lyndon 段:

• 用一个已确定分解的前缀,以及一个正在尝试扩展的候选段。
• 用两个指针分别指向候选段的当前比较位置和末尾,依据当前字符与前面对应字符的大小关系决定行为。
• 若当前字符大于比较位置字符,说明可扩展为更长的 Lyndon 串,重置比较指针继续。
• 若相等则两指针同步前进;若小于,则可以确定若干个完整的 Lyndon 串并输出,再从新位置重新开始。

由于每个字符至多被比较常数次,算法总时间为线性,且只需常数额外空间。

应用场景

Lyndon 分解及 Duval 算法可用于求字符串的最小循环表示、求最小和最大后缀、构造 Chen-Fox-Lyndon 定理相关结构,也与后缀数组、Runs 结构等字符串问题密切相关,是竞赛与文本处理中的实用工具。

常见问题

问:Lyndon 分解一定唯一吗?答:是的。Lyndon 分解定理保证任意字符串的 Lyndon 分解存在且唯一,这也是许多应用能成立的前提。

问:如何用它求最小表示?答:将字符串复制一份接在自身后面再做 Duval 分解,过程中跨越原串长度中点的 Lyndon 段起点即对应最小循环表示的起始位置。