一、Lyndon串的定义
一个非空字符串 ( s ) 称为 Lyndon串，当且仅当对于其所有真后缀 ( t )（即 ( t \neq s ) 且 ( t ) 是 ( s ) 去掉前若干字符后的子串），都有 ( s < t )（字典序比较）。
- 例：
"a"、"ab"、"abc"是 Lyndon 串，而"aa"、"abba"不是（因为"aa"的后缀"a"不大于自身，"abba"的后缀"bba"小于原串）。
二、Lyndon分解的概念
Lyndon分解 是将一个字符串 ( s ) 唯一分解为若干 Lyndon 串的序列 ( s = w_1w_2\cdots w_k )，满足 ( w_1 \geq w_2 \geq \cdots \geq w_k )（字典序非递增）。
- 唯一性：根据 Schützenberger 定理，每个字符串的 Lyndon 分解是唯一的。
三、Duval 算法（线性时间分解）
Duval 算法是高效计算 Lyndon 分解的方法，时间复杂度为 ( O(n) )，适用于长度为 ( n ) 的字符串。
算法步骤
- 初始化：设字符串为 ( s[0…n-1] )，指针 ( i = 0 )。
- 循环处理：当 ( i < n ) 时：
- 设 ( j = i )，( k = i + 1 )。
- 当 ( k < n ) 时：
- 若 ( s[k] > s[j] )：说明从 ( i ) 到 ( k ) 无法构成 Lyndon 串，直接分解出 ( s[i…j] )（但此时需先处理前面的部分，具体见步骤 3）。
- 若 ( s[k] == s[j] )：( j++ )（扩展当前可能的 Lyndon 串）。
- 若 ( s[k] < s[j] )：说明当前段 ( s[i…k] ) 是一个更小的 Lyndon 串，需要重置 ( j = i )（不扩展，因为当前字符更小，会破坏非递增顺序）。
- 分解出一个 Lyndon 串 ( s[i…k-1] )，并将 ( i ) 设为 ( k )。
伪代码
def lyndon_decomposition(s):n = len(s)i = 0decomposition = []while i < n:j = ik = i + 1while k < n and s[k] >= s[j]:if s[k] == s[j]:j += 1else:j = i # s[k] > s[j] 时，j 重置为 i，因为当前段可能更小k += 1# 此时 s[i..k-1] 是一个 Lyndon 串while i <= j:decomposition.append(s[i:i + k - j])i += k - jreturn decomposition
核心思想
- 通过双指针 ( j ) 和 ( k ) 维护当前可能的 Lyndon 串边界，确保每次分解出的子串是满足非递增条件的最大 Lyndon 串。
- 每个字符最多被访问两次，因此时间复杂度为线性。
四、应用场景
1. 最小循环同构（最小表示法）
给定一个字符串的循环同构（如 "abc" 的循环同构有 "abc"、"bca"、"cab"），求其中字典序最小的一个。
- 方法：将字符串 ( s ) 重复一次（如 ( s + s )），利用 Lyndon 分解找到长度为 ( |s| ) 的最小 Lyndon 子串，即为最小循环同构。
2. 字符串分解与周期性
- 分解为 Lyndon 串的乘积：根据 Lyndon 分解定理，任意字符串可唯一分解为非递增的 Lyndon 串序列，这在组合数学和形式语言理论中有重要应用。
- 检测重复子串：若一个字符串 ( s ) 的 Lyndon 分解中所有子串长度均为 ( d )，且 ( d ) 整除 ( |s| )，则 ( s ) 由某个子串重复构成（如 ( “ababab” ) 分解为 ( [“ab”, “ab”, “ab”] )）。
3. 字符串排序与等价类
- 在处理字符串的等价类（如循环同构类）时，Lyndon 分解可用于快速判断等价类中的最小代表元。
4. 算法竞赛与编程题
- 典型题目：LeetCode 1328. 破坏回文串（间接应用）、寻找字符串的最小循环移位等。
五、总结
Lyndon 分解是字符串处理中的重要工具，通过线性时间算法将字符串拆解为具有严格字典序性质的子串序列，广泛应用于最小表示法、周期性检测、组合数学等领域。掌握 Duval 算法的核心逻辑（双指针维护边界，利用字典序比较分解）是理解和应用的关键。