Lyndon 词与 Lyndon 分解

· · 算法·理论

基本约定与前置知识

\forall x \in A^+, w \in x^* \Rightarrow w = x \exists u, v \in A^*, \text{s.t. } x = uv, y = vu
更确切地说，$\exists u, v \in A^*, \text{s.t. } x = uv, y = vu$，此处的 $z$ 满足 $z \in u(vu)^*$。

5.1 Lyndon 词与 Lyndon 分解

定义 5.1.1 (字典序)

给定全序 (A, \leq)，定义 A^* 上的序 (A^*, \leq) 如下：

设 x, y \in A^*。\ (1) 当 x = \emptyset，令 x \leq y 恒成立。\ (2) 当 x \neq \emptyset, y = \emptyset，令 x \leq y 恒不成立。\ (3) 当 x, y \neq \emptyset，设 x = ax', y = by'，其中 a, b \in A, x', y' \in A^*，令 x \leq y 当且仅当 a < b \lor (a = b \land x' \leq y')。

称 (A^*, \leq) 为 A^* 上的字典序，容易验证其也为全序。

命题 5.1.2 (字典序的基本性质)

(1) \forall u, v, w \in A^*, u < v \Leftrightarrow wu < wv。\ (2) \forall u, v, w, x \in A^*, v \not\in uA^* \Rightarrow (u < v \Leftrightarrow uw < vx)。

Proof. 归纳即得。

定义 5.1.3 (Lyndon 词)

称 w \in A^+ 为 Lyndon 词，若其本原且在共轭类中字典序最小。这两个条件可以统摄为：

\forall u, v \in A^+, w = uv \Rightarrow w < vu

记所有 Lyndon 词构成集合 L \subset A^+。显然 A \subset L。

当 k = |A| 有限，由共轭类计数公式可知，长为 n 的 Lyndon 词的数量为：

\frac{1}{n} \sum_{d \mid n} \mu(d) k^{\frac{n}{d}}

例子 5.1.4

设 A = \{a, b\} \ (a < b)，则前若干个 Lyndon 词形如：

L = \{a, b, ab, aab, abb, aaab, aabb, abbb, \cdots\}

命题 5.1.5

设 w \in A^+，则 w 为 Lyndon 词当且仅当 w 小于其所有真后缀。或者形式化地说：

\forall w \in A^+, w \in L \Leftrightarrow (\forall u, v \in A^+, w = uv \Rightarrow w < v)

Proof. 先证充分性。由条件立即得到：

\forall u, v \in A^+, w = uv \Rightarrow w < v < vu

明所欲证。

再证必要性。首先说明 v 不为 w 的前缀。若不然 \exists t \in A^+, \text{s.t. } w = uv = vt，命题 1.3.4 指出：

\exists p, q \in A^*, i \in \mathbb{N}, \text{s.t. } u = pq, t = qp, v = p(qp)^i = (pq)^i p

进而有 w = p(qp)^{i + 1} = (pq)^{i + 1} p。由 w 为 Lyndon 词可知其本原性，随后易证 p, q \in A^+。再由其最小性可知：

\begin{array}{l} & w = (pq)^{i + 1} p < p(pq)^{i + 1} \\ \Rightarrow & (qp)^{i + 1} < (pq)^{i + 1} \\ \Rightarrow & (qp)^{i + 1} p < (pq)^{i + 1} p = w \end{array}

这与最小性矛盾，故证得 v 不为 w 的前缀。

由 |w| = |u| + |v| > |v| 显见 w \neq v。若 w > v，则 w > vu，与最小性矛盾。总之有 w < v。

推论 5.1.6

若 w \in A^+ 为 Lyndon 词，则其没有 border。

Proof. 考虑反证法：设 v 为 w 的 border，则一方面由真前缀的性质可知 v < w，另一方面由 命题 5.1.5 可知 w < v，矛盾！

命题 5.1.7

Proof. 先证充分性，只需讨论 w = lm 的情况。首先说明 w < m：

接下来分类讨论 w 的真后缀 v \neq m 的形态：

总之 w 小于其所有真后缀，故 w 为 Lyndon 词。

再证必要性，同样只需讨论 w \in L \backslash A 的情况。

设 m 为 w 的最长真 Lyndon 后缀（合法性：w 的最后一个字母为其真 Lyndon 后缀），w = lm，只需证明 l \in L。

设 v 为 l 的任一真后缀，m 的最长性指出 vm \not\in L。取 t 为 vm 的满足 t < vm 的一个真后缀（由 vm \notin L 及 命题 5.1.5 知其存在，且 t 也是 w = lm 的真后缀）。

若 v < t，则由 v < t < vm 可归纳得 \exists s \in A^+, \text{s.t. } t = vs，且 s 为 m 的真后缀。

故由 t = vs < vm 可知 s < m，根据 命题 5.1.5 这与 m \in L 矛盾，因此 v \geq t。

进而根据 命题 5.1.5 可知 l < lm = w < t \leq v，因而 v 的任意性和 命题 5.1.5 指出 l \in L。

最终，w \in L 指出 w < m，接下来分类讨论 l 与 m 的关系：

总之，我们给出了分解 w = lm，且满足 l, m \in L, l < m。

上述命题的必要性证明也给出了一个递归构造 Lyndon 词的方法；同时，对于每个 w \in L \backslash A 也提供了一种分解为 Lyndon 词之积的方式。下面给它一个名称。

定义 5.1.8 (标准分解)

设 w \in L \backslash A，m 为 w 的最长真 Lyndon 后缀，w = lm，则 l, m \in L, l < m，称 \sigma(w) = (l, m) 为 w 的标准分解。

Remark. Lyndon 词按照 命题 5.1.7 的叙述分解时所得结果未必唯一，例如 aababb = (a)(ababb) = (aab)(abb) = (aabab)(b)，其中前者为标准分解。

定理 5.1.9 (Lyndon 分解定理)

设 w \in A^+，则其可唯一表作递降的 Lyndon 词之积。或者形式化地说：

\exists ! (n \in \mathbb{N}_+, [l_1, \cdots, l_n] \in L^n), \text{s.t. } w = l_1 \cdots l_n, l_1 \geq \cdots \geq l_n

Proof. 先证存在性。首先由于 w 的每个单字母都是 Lyndon 词，w 总能表作若干 Lyndon 词之积，故可选取一种分解方式，使得 n 最小。

断言这种分解满足 l_1 \geq \cdots \geq l_n：不然，设 l_i < l_{i + 1}，由 命题 5.1.7 可知 l_i l_{i + 1} \in L，则把 l_i, l_{i + 1} 合起来也是一种合法的分解，与 n 的最小性矛盾。

再证唯一性。设 (n, [l_1, \cdots, l_n]), (n', [l'_1, \cdots, l'_{n'}]) 都满足条件，考虑对 n 归纳：

为了求解 Lyndon 分解，一个自然的想法是“剥洋葱”——即逐步析出分解中的首项或末项。下面阐述了有关这两项的一些性质。

命题 5.1.10

设 w \in A^+ 的 Lyndon 分解为 w = l_1 \cdots l_n，则：\ (1) l_n 为 w 的最小非空后缀。\ (2) l_n 为 w 的最长 Lyndon 后缀。\ (3) l_1 为 w 的最长 Lyndon 前缀。

Proof. (1) 设 v 为 w 的最小非空后缀，w = uv。v 的任何真后缀也是 w 的后缀（且比 v 长），因 v 是 w 的最小后缀，故 v 严格小于其所有真后缀，由 命题 5.1.5 可知 v \in L。

若 u = \emptyset，命题显然正确。否则，令 v' 为 u 的最小非空后缀，u = sv'。

若 v' < v，则由 命题 5.1.7 可知 v' v \in L，故由 命题 5.1.5 可知 v' v < v，与 v 的最小性矛盾。

故有 v' \geq v，据此可以递归拆解出 w = v_1 \cdots v_n，满足 v_1 \geq \cdots \geq v_n，再根据 定理 5.1.9 的唯一性可见这无非是 l_i = v_i，遂得证。

(2) 设 s 为 w 的任一 Lyndon 后缀，则由 (1) 可知 l_n \leq s。

若 |l_n| < |s|，则 l_n 为 s 的后缀，由 s \in L 和 命题 5.1.5 可知 s < l_n，矛盾！

故 |l_n| \geq |s|，由 s 的任意性即得 l_n 为 w 的最长 Lyndon 后缀。

(3) 设 p 为 w 的任一 Lyndon 前缀。

若 |p| > |l_1|，设 p = l_1 \cdots l_i u，其中 1 \leq i < n，u 为 l_{i + 1} 的非空前缀。

由 p \in L 和 命题 5.1.5 可知 p < u，而 u \leq l_{i + 1} \leq l_1 \leq p，矛盾！

故 |p| \leq |l_1|，由 p 的任意性即得 l_1 确为最长的 Lyndon 前缀。

上面命题 (1) 给出了一种直截了当但效率不高——每次拆出一个最小非空后缀；接下来讨论另一种思路——增量式维护前缀，这正是大名鼎鼎的 Duval 算法。

让我们来刻画 Lyndon 词的前缀。记 P 为所有作为某个 Lyndon 词的前缀的词的集合：

P = \{w \in A^+ \mid wA^* \cap L \neq \varnothing\}

显见 L \subset P。下面来研究一种特殊的、在后端添加单字母的情况。

推论 5.1.11

设 u, v \in L, u < v，则 \forall k, k' \in \mathbb{N}_+, u^k v^{k'} \in L。

Proof. 由 命题 5.1.7 立即可得。

命题 5.1.12

设 u \in A^*, v \in A^+, uv \in L，若 a \in A, v < a，则 ua \in L。

Proof. u = \emptyset 的情况是显然的，下设 u \neq \emptyset。

设 s = u' a 为 ua 的真后缀，则 u' 为 u 的后缀且 u' \neq u，故 u' v 为 uv 的真后缀。

由 uv \in L 和 v < a 可知 uv < u' v < u' a，若 u \in u' aA^*，则有 u' a < uv，矛盾。

故 u \not\in u' aA^*，则 u < u' a，进而 ua < u' a，由 u' 的任意性即证得 ua \in L。

引理 5.1.13

设 w = (uav')^k u，其中 u, v' \in A^*, a \in A, k \in \mathbb{N}_+, uav' \in L，则：\ (1) \forall a' \in A, a' > a \Leftrightarrow wa' \in L。

Proof. (1) 先证必要性。假设 a' \leq a，则 wa' = (uav')^k ua' \leq ua，故 wa' \not\in L。

再证充分性。由 a < a' 可知 av' < a'，再由 命题 5.1.12 可知 ua' \in L，并有 uav' < ua'。据 uav' \in L 和 推论 5.1.11 即得 wa' = (uav')^k (ua') \in L。

下面先对 P 的定义加以扩展，定义 P'：

P' = \begin{cases} P, &\quad A \text{ 中无最大元} \\ P \sqcup \{c^k \mid k \in \mathbb{N}_{\geq 2}\}, &\quad A \text{ 中有最大元 } c \end{cases}

在此基础上阐述 a' \leq a 时的结论：

(2) wa \in P' \backslash L。\ (3) \forall a' \in A, a' < a \Rightarrow wa' \not\in P'。

Proof. (2) 当 A 中无最大元，取 c \in A 使之大于 uav' 中出现过的所有字母，则容易验证 (uav')^{k + 1} c \in L。

当 A 中有最大元 c，若 uav' 退化为 c 则 wa = c^{k + 1} \in P'，否则断言 uav' < c（不然其以 c 开头，这将导出其只含 c，矛盾），由 推论 5.1.11 即得 (uav')^{k + 1} c \in L。

(3) 对任意 h \in A^*，wa'h = (uav')^k u a' h 有真后缀 ua' h。比较两者：wa'h 以 ua 开头（取第一个 uav' 周期），ua'h 以 u 开头接 a'。在位置 |u| + 1 处，wa'h 有 a，ua'h 有 a'。由 a > a' 得 wa'h > ua'h，与 Lyndon 词须小于所有真后缀（命题 5.1.5）矛盾。故 \forall h, wa'h \notin L，从而 wa' \notin P'。

上面引理的结论提示我们，P' 的中的元素似乎总能表示为某一 Lyndon 词重复多次、再加上一个不完整的周期。形式化地说，记 S 为所有 Lyndon 词的 严格半幂 (strict sesquipower) 构成的集合：

S = \{(uv)^k u \mid u \in A^*, v \in A^+, uv \in L, k \in \mathbb{N}_+\}

命题 5.1.14 (前缀候选集 \Leftrightarrow 严格半幂集)

Proof. S \subset P' 部分的证明同 引理 5.1.13 (2)，不再赘述。

下证 P' \subset S。首先显见 L \subset S，其次需证 P' \backslash L \subset S，考虑对长度归纳：

综上，明所欲证。

命题 5.1.15 (前缀增量时标准分解式的变化)

设 u, v' \in A^*, a \in A, k \in \mathbb{N}_+, uav' \in L，记 \text{CFL}(x) 为 x \in A^* 的标准分解式。\ (1)

\text{CFL}((uav')^k u) = (uav')^k \cdot \text{CFL}(u)

(2) 设 w = (uav')^k ua' h，其中 a' \in A, h \in A^*, a' < a，则：

\text{CFL}(w) = (uav')^k \cdot \text{CFL}(ua' h)

Proof. (1) 设 (uav')^i s 为 (uav')^k u 的 Lyndon 前缀，其中 1 \leq i \leq k，s 为 u 的前缀。

综上，在 (uav')^k u 的长度 \geq |uav'| 的前缀中只有 uav' 这一个为 Lyndon 词，故其最长 Lyndon 前缀为 uav'。随后对 k 归纳便明所欲证。

(2) 由 引理 5.1.13 (3) 可知 (uav')^q ua' \not\in P'，故据 命题 5.1.10 (3) 可得 w 的标准分解式的首项为 (uav')^q u 的最长 Lyndon 前缀：同 (1) 可见这无非是 uav'。随后同样对 k 归纳即得。

算法 5.1.16 (Duval 算法)

输入：词 w \in A^+。\ 输出：分解式序列 [l_1, \cdots, l_n] \in L^n，满足 w = l_1 \cdots l_n, l_1 \geq \cdots \geq l_n。\ 状态类别：三元组 ([l_1, \cdots, l_n], \text{null}, w) 或 ([l_1, \cdots, l_n], (u, av', k), w)。\ 初始状态：([], \text{null}, w)。\ 转移 I / 析出：([l_1, \cdots, l_n], \text{null}, aw') \Rightarrow ([l_1, \cdots, l_n], (\emptyset, a, 1), w')\ 转移 II / 大字移进：当 a' > a，([l_1, \cdots, l_n], (u, av', k), a' w') \Rightarrow ([l_1, \cdots, l_n], (\emptyset, (uav')^k ua', 1), w')\ 转移 III / 同字移进：([l_1, \cdots, l_n], (u, av', k), aw') \Rightarrow ([l_1, \cdots, l_n], (ua, v', k), w')\ 转移 IV / 周期更新：([l_1, \cdots, l_n], (u, \emptyset, k), w) \Rightarrow ([l_1, \cdots, l_n], (\emptyset, u, k + 1), w)\ 转移 V / 词尾：([l_1, \cdots, l_n], (u, av', k), \emptyset) \Rightarrow ([l_1, \cdots, l_n] + [uav']^k, \text{null}, u)\ 转移 VI / 小字移进：当 a' < a，([l_1, \cdots, l_n], (u, av', k), a' w') \Rightarrow ([l_1, \cdots, l_n] + [uav']^k, \text{null}, ua' w')\ 终止状态：([l_1, \cdots, l_n], \text{null}, \emptyset)，此时输出 [l_1, \cdots, l_n]。

正确性证明： 算法维护的不变式为，当状态为 ([l_1, \cdots, l_n], (u, av', k), a' w') 时，已输出的部分 [l_1, \cdots, l_n] 满足 l_1, \cdots, l_m \in L, l_1 \geq \cdots \geq l_m，而未输出部分的前缀 (uav')^k u 满足 uav' \in L。各转移规则的正确性依据如下：

每次析出后，输出序列仍单调不增：因为新析出的 uav'（k 个）不小于之前已析出的任何因子（由不变式保证递减），且 a' < a 保证了下一批因子将更小。

时间复杂度： 将比较分为两类：

综上，总比较次数 \leq 2|w|，而周期更新的次数不会超过同字移进的次数故也 \leq |w|，因而总时间复杂度为 O(|w|)。

实现中，可以用指针 i 指示未输出部分的开头，用指针 j 指示当前匹配到周期中对应位置的下标，用指针 k 指示当前未处理的首个字符的下标，详见代码。

实现（Luogu P6114 【模板】Lyndon 分解）：

#include <stdio.h>
#include <string.h>

int pos[5000001];
char s[5000001];

int lyndon_decomposite(char s[], int ans[]){
    int n = strlen(s), m = 0;
    int i = 0;
    while (i < n){
        int j = i, k = i + 1;
        while (k < n && s[k] >= s[j]){
            if (s[k] > s[j]){
                j = i;
            } else {
                j++;
            }
            k++;
        }
        int d = k - j;
        while (i <= j){
            i += d;
            ans[m++] = i;
        }
    }
    return m;
}

int main(){
    scanf("%s", s);
    int m = lyndon_decomposite(s, pos), ans = 0;
    for (int i = 0; i < m; i++){
        ans ^= pos[i];
    }
    printf("%d", ans);
    return 0;
}

Reference