Lyndon 串和 Lyndon 分解

定义

Lyndon 串 (Lyndon Word) 又称简单串，它的一种定义是，字典序严格小于自己的所有真后缀的字典序的字符串。另一种定义是，字典序严格小于自己的所有非平凡循环同构串的字典序的字符串。

这两种定义事实上是等价的。我们只需要用下面两个浅显的命题说明。

若 $s$ 存在字典序小于等于自己的真后缀，则 $s$ 也存在字典序小于等于自己的非平凡循环同构串

设 $B$ 是一个字典序小于等于 $s$ 的真后缀，即 $B \le s$；且 $s$ 能表示为 $A$ 和 $B$ 两个字符串拼接的形式，即 $s=AB$。

显然，$BA$ 是 $s$ 的一个非平凡循环同构串。设 $C$ 为 $s$ 的长度为 $|B|$ 的前缀，设 $D$ 为一个可与 $C$ 拼接成 $s$ 的字符串 ($s=CD$)。

• 若 $B < C$，则 $BA < CD = s$。$BA$ 是一个字典序小于等于 $s$ 的非平凡循环同构串。

• 若 $B=C$，且 $A \le D$，则 $BA \le CD = s$。$BA$ 是一个字典序小于等于 $s$ 的非平凡循环同构串。

• 若 $B=C$，且 $A > D$，则 $DC < AB = s$。$DC$ 是一个字典序小于等于 $s$ 的非平凡循环同构串。

若 $s$ 存在字典序小于等于自己的非平凡循环同构串，则 $s$ 也存在字典序小于等于自己的真后缀

设 $BA$ 是一个字典序小于等于 $s$ 的非平凡循环同构串，即 $BA \le s$；且 $s$ 能表示为 $A$ 和 $B$ 两个字符串拼接的形式，即$s=AB$

则 $B \le BA \le s$。$B$ 是一个字典序小于等于 $s$ 的真后缀。

第二种定义说明，一个非循环字符串的字典序最小的循环同构串是一个 Lyndon 串，而一个循环字符串的所有循环同构串都不是 Lyndon 串。

如果 $a,b$ 都是 Lyndon 串，则当且仅当 $a<b$ 时 $ab$ 是一个 Lyndon 串。

Lyndon 串的前缀不一定是 Lyndon 串。$\texttt{aa}$ 是 $\texttt{aab}$ 的前缀，但它不是 Lyndon 串。

Lyndon 分解

对于一个字符串 $s$，存在且仅存在一种对它的划分 $s = w_1w_2 \ldots w_m$，满足 $w_1, w_2, \ldots w_m$ 都是 Lyndon 串且 $w_1 \ge w_2 \ge \ldots \ge w_m$。这种划分被称为 Lyndon 分解 (Lyndon Decomposition)。

证明

单个字符组成的字符串是 Lyndon 串。因此至少存在一种对 $s$ 的划分，满足 $w_1, w_2, \ldots w_m$ 都是 Lyndon 串。

若 $w_{i} < w_{i+1}$，则 $w_{i}w_{i+1}$ 也是一个 Lyndon 串。用 $w_{i}w_{i+1}$ 替换所有 $w_{i} < w_{i+1}$，一定可以得到一个满足 $w_1 \ge w_2 \ge \ldots \ge w_m$ 的划分。故任何字符串都至少存在一种 Lyndon 分解。

假设 $s$ 存在两个或更多不同的 Lyndon 分解，设其中两个分别为 $a_1, a_2, \ldots, a_n$ 和 $b_1, b_2, \ldots, b_m$。取它们第一个满足 $a_i \neq b_i$ 的位置 $i$。

如图，令 $a_j$ 为穿过 $b_i$ 的最后一个字符的子串。设 $c$ 为 $b_i$ 和 $a_j$ 的公共部分，我们有 $b_i > a_i \ge a_j > c$，而 $c$ 是 $b_i$ 的一个真后缀，因此 $b_i$ 不是一个 Lyndon 串，这与假设矛盾。

在 Lyndon 分解中，$w_1$ 一定是最长的为 Lyndon 串的前缀，$w_m$ 一定是最长的为 Lyndon 串的后缀。

由于 $w_1 \ge w_2 \ge \ldots \ge w_m$，且 $w_m$ 严格小于它的所有真后缀，$w_m$ 一定是 $s$ 的最小后缀。

最小表示法

求 $s$ 所有循环同构串中最小的那一个。

显然这个东西可以后缀数组求，但我们要考虑如何使用 Lyndon 分解做。

若这个字符串不是循环串，则它所有循环同构串中最小的那一个一定是一个 Lyndon 串。那么 $ss$ 的 Lyndon 分解中，一定有一个子串包含这个最小表示。由于往后是它的前缀，往前是它的后缀，所以这个子串一定不会和两边合并，就是这个最小表示。

若这个字符串是一个循环串，则我们只需要把循环节抽出来求最小表示。

上面两种情况可以归纳到一起。

for(int i = 1; i <= n; ++i) std::scanf("%d", a + i);
for(int i = n + 1; i <= n + n; ++i) a[i] = a[i - n];
ans = 1;
for(int i = 1; i <= n + n; ){
    int j = i, k = i;
    while(k + 1 <= n + n && a[j] <= a[k + 1]){
        if(a[j] == a[k + 1]) ++j, ++k;
        else j = i, ++k;
    }
    while(i <= j){
        i += k - j + 1;
        if(i <= n) ans = i;
    }
}
for(int i = ans; i <= ans + n - 1; ++i)
    std::printf("%d ", a[i]);

评论