Lyndon

题目描述 定义 Lyndon Word：\(s\) 是 Lyndon Word 当且仅当 \(s\) 是其所有后缀中最小的一个串。 给定字符串 \(s\) ，请把这个字符串分成若干个子串，使得每个子串都是 Lyndon Word 。并且从左到右每个字符串都大于等于下一个。 最后输出每一个子串右端点异 ......

### 什么是 $Lyndon$ 串 我们定义一个串是 $Lyndon$ 串，当且仅当这个串的**最小后缀**就是这个串本身。 也就是说 $Lyndon$ 串等价于这个串是它的所有循环表示中**字典序最小**的。 ### $Lyndon$ 分解定义 将一个字符串 $S$ 分解为若干个子串：$s_1s ......

Lyndon 串：$s<{\rm suf}'(s)$ 的串 $s$ 为 Lyndon 串。 引理 1：若 $u$、$v$ 为 Lyndon 串，$u<v$，则 $uv$ 也为 Lyndon 串。 引理 2：若 $uc$ 为 Lyndon 串的前缀，则 $uc'(c'>c)$ 为 Lyndon 串。 ......

现在只会 lyndon 分解怎么写。所以先放在这里占坑。以后补 Runs 和 Lyndon Tree 相关知识。 大量抄 pdf 和 cmd 博客。 Lyndon Word 及其相关性质 定义：若字符串 $s$ 的最小后缀是它本身，则它是一个 Lyndon Word。 Lyndon Word 没有 ......

神秘科技。 定义一个串为 Lyndon 串，当且仅当这个串的最小表示法是它本身。 定义一个串的拆分为 Lyndon 分解，当且仅当每个拆分都是 Lyndon 串，且 $s_i\geq s_{i+1}$。 求出某个串的 Lyndon 分解可以用 Duval 算法，该算法可以 $O(n)$ 求出这个串的 ......