Lyndon分解和最小循环表示学习

做CF594E涉及的两个知识点。以下字符串采用Python记法。

Lyndon分解

定义 $S$ 是Lyndon串，当且仅当对于任意有意义的正整数 $i$ 有 $S<S[i:]$.

定义 $S$ 的Lyndon分解是一个Lyndon串的序列 $s_1, s_2, \ldots, s_n$, 使得 $S=s_1s_2 \cdots s_n$ 并且 $s_1 \ge s_2 \ge \cdots \ge s_n$.

Lyndon分解存在且唯一。

不难发现，Lyndon分解可以这么得到：对于 $S$, 取最小的后缀 $S[i:]$, $S$ 的Lyndon分解，是在 $S[:i]$ 的Lyndon分解的最后加上一项 $S[i:]$ 得到的序列。

于是，Lyndon分解可以用后缀数组求，但是这样太复杂了。

Lyndon分解的Duval算法：

设原字符串为 $S$. 逐个加入字符，设已能确定 $S[:i]$ 的Lyndon分解 $s_1, s_2, \ldots, s_n$ 为 $S$ 的Lyndon分解的前缀，再尽可能地扩充字符串 $S[i:k]$, 使得 $S[i:k]$ 的最小周期 $t$ 是Lyndon串。考虑加入字符 $S_k$.

• 若 $S_k<S_{k-|t|}$, 则 $S[i:k+1]$ 的最小周期就不是Lyndon串了，不过此时 $S[:i+n|t|]$ 的Lyndon分解已确定，即在 $S[:i]$ 的基础上加入 $n$ 个 $t$, 取新参数 $i‘=j‘=i+n|t|, k‘=i‘+1$ 重来。
• 若 $S_k=S_{k-|t|}$, 则 $t$ 也是 $S[i:k+1]$ 的最小周期。
• 若 $S_k>S_{k-|t|}$, 则 $S[i:k+1]$ 的最小周期是其本身，且仍然为Lyndon串。

实现上我们只需要维护 $i, k$ 以及 $j=k-|t|$. 代码链接

该算法时间 $O(|S|)$, 除去输入输出只需要 $O(1)$ 额外空间，是一个非常简短而高效的算法。

最小循环表示

最小循环表示，也就是对于字符串 $S$, 求出最小的 $S_i=S[i:]S[:i]$.

最小循环表示可以基于比较地求。

具体地说，我们维护两个“可能是最小循环表示”的决策 $i,j$ 并加以检验。

我们通过枚举比较求出 $S_i$ 和 $S_j$ 的最长公共前缀 $k$. 初始时，设 $i=0, j=1$, 不妨设始终有 $i<j$, 若 $j \ge n$ 则算法停止，答案为 $i$.

• 若 $S_i=S_j$, 我们已经找到了解。
• 若 $S_i<S_j$, 说明 $[j, j+k]$ 内的整数不是最小循环表示，因为它总比 $[i, i+k]$ 内的对应决策劣，因此令 $j \gets j+k+1$.
• 若 $S_i>S_j$, 同理令 $i \gets i+k+1$.

此后将 $i,j$ 排好序，若 $i=j$ 则令 $j \gets j+1$. 用新的 $i, j$ 重复此过程。

证明不是太显然，如果2019年内没有填上就是鸽了。