Lyndon 小记

神秘科技。

定义一个串为 Lyndon 串，当且仅当这个串的最小表示法是它本身。

定义一个串的拆分为 Lyndon 分解，当且仅当每个拆分都是 Lyndon 串，且 \(s_i\geq s_{i+1}\)。

求出某个串的 Lyndon 分解可以用 Duval 算法，该算法可以 \(O(n)\) 求出这个串的 Lyndon 分解。

这个算法的流程如下：我们维护原串的某个拆分 \(s_1,s_2,s_3\)，其中 \(s_1\) 表示已经拆分好了的 Lyndon 分解，\(s_2\) 表示某个 Lyndon 串的若干循环。具体的，设 \(w\) 为某个长度为 \(l\) 的 Lyndon 串，则 \(s_2\) 可以表示为 \(ww\dots ww[1,i]\)，其中 \(1\leq i\leq l\)。\(s_3\) 表示尚未处理的串。

假设 \(s_2\) 的开始位置为 \(i\)，\(s_3\) 的开始位置为 \(j\)，\(j\) 减去 \(s_2\) 那个循环的 Lyndon 串长的位置为 \(k\)。 则我们分类讨论 \(c_j\) 与 \(c_k\) 的大小关系：

• 如果 \(c_j=c_k\)，那么循环可以扩展一位，则 \(j,k\) 同时加一。
• 如果 \(c_j>c_k\)，则 \(c[i,j]\) 可以视作一个新的 Lyndon 串，那么令 \(k\) 回到初始位置，然后 \(j\) 加一。
• 如果 \(c_j<c_k\)，则 \(c[i,j]\) 不是某个 Lyndon 串的循环了，那么我们将已经有的 Lyndon 串的循环节依次截取出来加入 \(s_1\)，最后剩下循环了一半的位置，更新 \(i\) 之后让 \(j\) 从 \(i+1\) 重新开始即可。

不难证明过程中满足 Lyndon 分解的性质。

那么复杂度呢？可以对几个指针分别讨论，\(i\) 显然是 \(O(n)\) 的，\(j,k\) 每次只会至多加一因此也是 \(O(n)\) 的。那么总的复杂度就是 \(O(n)\) 的。

模板题 的 提交记录