字符串，太深刻了 /kk

定义

下标从 1 开始。

\(+\) 是字符串拼接。

\(|s|\) 表示 \(s\) 的长度。

\(s_i\) 表示 \(s\) 的第 \(i\) 个字符。

\(s^k\) 表示 \(k\) 个 \(s\) 拼接的结果。

字符串间的大小关系用字典序比较。

Lyndon 串

字符串 \(s\) 是 Lyndon 串当且仅当 \(s\) 小于其每个非空后缀。

有的文章里的“简单串”就是 Lyndon 串。

Lyndon 分解

若字符串 \(s=w_1+\dots+w_k\)，且 \(w_1\dots w_k\) 都是 Lyndon 串，且 \(w\) 字典序单调不增（\(w_i\ge w_{i+1}\)），

则 \(w_1\dots w_k\) 是 \(s\) 的 Lyndon 分解。

引理 1：\(s\) 字典序最小的后缀为 \(w_k\)。

证明：任意 \(w_i\) 都小于其每个非空后缀，所以从 \(w_i\) 起头一定比从 \(w_i\) 中间起头（也就是以 \(w_i\) 的某个非空后缀起头）优，

而 \(w_k\) 小于 \(w_i(i\ne k)\)，所以从 \(w_k\) 起头一定比从 \(w_i\) 起头优，则肯定从 \(w_k\) 起头，这个后缀就是 \(w_k\)。

引理 2：Lyndon 分解唯一存在。

证明：由引理 1 可以唯一确定 \(w_k\)，而 \(w_1\dots w_{k-1}\) 一定是 \(s\) 去掉 \(w_k\) 后的串的 Lyndon 分解，于是可以确定 \(w_{k-1}\)，

以此类推，可以唯一确定 \(w_1\dots w_k\)。

由引理 2 可以轻松得到一个 \(O(n^2)\) 的 Lyndon 分解算法，但是这显然不是我们想要的。

Duval 算法可以 \(O(n)\) 求出 Lyndon 分解。

定义字符串 \(s\) 是近似 Lyndon 串，当且仅当 \(s=w^kw'\)，其中 \(w\) 是任意 Lyndon 串，\(k\ge 1\)，\(w'\) 是 \(w\) 的前缀（可以空）。

划分 \(s=s_1+s_2+s_3\)，其中 \(s_1\) 的 Lyndon 分解已经得出，\(s_2\) 是一个近似 Lyndon 串，\(s_3\) 无要求，

初始 \(s_1\) 为空，\(s_2\) 是 \(s\) 的第一个字符（单字符肯定是近似 Lyndon 串），\(s_3\) 是 \(s\) 去掉第一个字符后的串，

现在需要调整划分方案，使得 \(s_1=s\)，\(s_2\) 和 \(s_3\) 为空。

设 \(s_2=w^kw'\)，\(x=w_{|w'|+1}\)，尝试每次去掉 \(s_3\) 开头的字符 \(y\) 加到 \(s_2\) 末尾，考虑 \(x,y\) 的关系：

• \(x=y\)：\(w^kw'+x\) 仍是近似 Lyndon 串，无需调整划分方案，更新一下 \(w'\) 即可。
• \(x<y\)：\(w^kw'+y\) 是 Lyndon 串。

证明：设 \(t=w^kw'+y\)。需要证明 \(t\) 字典序最小的后缀是 \(t\) 本身。
引理 1 已经证过从 \(w\) 起头一定比从 \(w\) 中间起头优，
由 \(x<y\) 得 \(w'+y>w\)，而从第 \(i(i\ne 1)\) 个 \(w\) 起头比从第一个 \(w\) 起头先走到 \(w'+y\)，
则从第一个 \(w\) 起头一定比从第 \(i\) 个 \(w\) 起头优，则肯定从第一个 \(w\) 起头，这个后缀就是 \(t\) 本身。

Lyndon 串肯定也是近似 Lyndon 串，所以也无需调整划分方案，

但 \(w'+y\) 并不是 \(w\) 的前缀，所以需要更新 \(w=t\)，\(w'=\varnothing\)。

• \(x>y\)：\(w^kw'+y\) 啥也不是，必须调整划分方案。把 \(k\) 个 \(w\) 划分进 \(s_1\)，令 \(s_2\) 为 \(s_1\) 后第一个字符，\(s_3\) 为剩下的串即可。