反对 George1123 偷学主义
反对 George1123 偷学主义
反对 George1123 偷学主义
反对 George1123 偷学主义

Lyndon 串

定义

如果一个串的最小后缀就是这个串本身，那这个串是 Lyndon 串。
例：\(abc\) 是 Lyndon 串，而 \(ba\) 不是。

定理

1. 如果 \(u\) 是Lyndon 串，\(v\) 是 Lyndon 串，且 \(u < v\)，那么 \(uv\) 也是 Lyndon 串。
   证明：如果 \(|u|\) 不是 \(v\) 的前缀，\(uv > v\)，得证。
   否则如果 \(uv\) 不是 Lyndon 串，那么 \(v > uv\)，那么如果把这两个字符串去掉前 \(|u|\) 个字符，\(v[|u| + 1, |v|] < v\)，与 \(v\) 是 Lyndon 串矛盾。
2. 若字符串 \(A\) 和字符 \(x\) 满足 \(Ax\) 是 Lyndon 串的前缀，且 \(y > x\)，那么 \(Ay\) 是 Lyndon 串。
   显然
   证明：如果这个串是 \(A + x + B\)。
   \(\forall l \in [2, n], A[l:] + x + B > A + x + B\)，\(A[l:] + x \ge A\)，因此 \(A[l:] + x > A[l:] + b \ge A\)。
   对于 \(l = n + 1\)，\(y > x \ge A_1\)，成立。

Lyndon 分解

定义一个串的 Lyndon 分解把他划分成一些串 \(A_1 A_2 A_3 ... A_m\)，满足：

1. \(A_1, A_2, ... A_m\) 都是 Lyndon 串。
2. \(\forall i \in [1, m - 1], A_i \ge A_{i + 1}\)

Lyndon 分解的存在性

可以先把一个串 \(S\) 拆分成 \(|S|\) 个字符。

如果存在一个串 \(A_i < A_{i + 1}\)，那么可以把 \(A_i\) 和 \(A_{i + 1}\) 合并起来。这样就得到了一个 Lyndon 分解。

Lyndon 分解的唯一性

如果存在两个不同的 Lyndon 分解：

\(A_1 A_2 A_3 ... A_m\)

\(B_1 B_2 B_3 ... B_m\)

找到第一个不满足 \(A_i \neq B_i\) 的位置 \(i\)。不妨 \(|A_i| > |B_i|\)。如果 \(A_i\) 在 \(B\) 中是 \(B_i B_{i+1} B_{i + 2} ... B_{k}[: l]\)。

那么 \(A_i < B_{k} [:l] \le B_{k} \le B_{k - 1} \le ... \le B_{i} < A_i\)，矛盾。

Duval 算法

维护三个变量 \(i, j, k\)。\([1, i - 1]\) 是确定了的分解(\(s_1 s_2 ... s_d\))。\(s[i, k - 1]\) 是待确定的分解，形式是 \(A^x B\)，满足 \(s[i, k - 1] > s_d\) 。让 \(j\) 为和 \(k\) 匹配的指针，为 \(k - |A|\)。

接下来分三类讨论：

1. 如果 \(s_j = s_k\)，那么匹配成功，继续匹配
2. 如果 \(s_j < s_k\)，那么 \(s[i, k]\) 是一个 Lyndon 串(Lyndon 串的定理 \(2\))，作为一个新的循环。
3. 如果 \(s_j > s_k\)，那么 \(s[i, k]\) 不是一个 Lyndon 串了，于是可以把这个 \(t^h\) 给确定出来作为 Lyndon 串，然后再进行匹配。