Lyndon 串相关知识速记

标签：后缀 知识 ge Lyndon 速记 cdots 引理 Lambda

Lyndon Words

一个串为 Lyndon 串当且仅当其为其所有后缀中字典序最小的.

Lyndon 分解：将一个串 \(w\) 分解为若干个字典序单调不增的 Lyndon 串 \(w_1, w_2, \cdots, w_k\) 的拼接，每个 \(w_i\) 为 \(w\) 的 Lyndon 因子.

可以证明一个串的 Lyndon 分解是存在且唯一的.

引理 1：若 \(u, v\) 均是 Lyndon 串且 \(u < v\)，则 \(uv\) 也是 Lyndon 串.

分讨易证.

---

引理 2：Lyndon 分解的最后一个 Lyndon 串为原串的最小后缀.

由 Lyndon 分解的单调性及 Lyndon 串的性质易证.

考虑每个单个字符都是 Lyndon 串，由引理 1 不断合并，可以得到一组合法的 Lyndon 分解；由最小后缀的唯一性，利用引理 2 归纳，可以导出 Lyndon 分解的唯一性.

可以将相同的 Lyndon 串写成幂的形式，即 \(w= w_1^{p_1}w_2^{p_2}\cdots w_k^{p_k}\).

---

Duval 算法：称形如 \(u^ku'\) 的串为近似 Lyndon 串，其中 \(u\) 为 Lyndon 串，\(u'\) 为 \(u\) 的一个前缀. 增量维护近似 Lyndon 串即可，也是 \(\mathcal{O}(|w|)\).

---

Significant Suffix

记 \(\operatorname{minsuf}(u)\) 为 \(u\) 的最小后缀，记 \(\operatorname{minsuf}(u, v) = \min_{w\in \operatorname{suf}(u)}wv\).

对于字符串 \(w\) 的后缀 \(w'\)，若存在字符串 \(v\) 使得 \(w'v\) 为字符串集合 \(\{w''v|w''\in \operatorname{suf}(w)\}\) 中字典序最小的元素，则称 \(w'\) 为 \(w\) 的 Significant Suffix. 将字符串 \(w\) 的所有 Significant Suffix 组成的集合记做 \(\Lambda(w)\).

---

引理 3：

\[v < uv < u^2v < \cdots < u^\infty \]

和

\[v > uv > u^2v > \cdots > u^\infty \]

两条不等式链中一定恰有一条成立.

证明考虑 \(v < uv\) 和 \(v > uv\) 中恰有一条成立，反复运用即可.

---

引理 4：\(\Lambda(w)\) 的元素形如 \(w_i^{p_i}\cdots w_k^{p_k}\)，将这个串记做 \(s_i\).

首先由 Lyndon 串的性质，一定形如 \(w_i^tw_{i+1}^{p_{i+1}}\cdots w_{k}^{p_k}\)，再由引理 3 可知当 \(t\in(0, k_i)\cap \mathbb N\) 时都无法取到最值.

（似乎？）可以证明这里的 \(s_i\) 的字典序是单减的，考虑反证

若 \(s_{i+1}> s_{i}\)，则 \(s_{i+1}>w_i^{p_i}s_{i+1}\)，由引理 3 知 \(s_{i+1}>w_{i}^\infty\)，那么存在 \(j\in[i+1, k]\cap \mathbb N\) 和 \(w_i\) 的某个后缀 \(w'_i\) 使得 \(w_j>w'_i>w_i\)，与 Lyndon 分解的性质矛盾.

---

显然有 \(\forall s\in \Lambda(w), \nexists s', s'\vartriangleleft s\)

再由 \(s_i\) 的单调性，\(s_i\) 为 Significant Suffix 的一个必要条件是 \(s_i\sqsupset s_{i+1}\).

引理 5：\(s_i\sqsupset s_{i+1} \iff w_i\sqsupset s_{i+1} \iff i \ge \lambda\)，其中 \(s_\lambda\) 为 Duval 算法中第一次比较完字符串末尾时的近似 Lyndon 串.

由 Duval 算法的过程易证.

实际上 \(i\ge \lambda\) 也是 \(s_i\in \Lambda(w)\) 的必要条件，于是可以 \(\mathcal{O}(|w|)\) 求出 \(\Lambda(w)\).

---

引理 6：对于 \(u, v\in\Lambda(w)\)，若 \(|u|<|v|\)，则 \(2|u|\le |v|\)，于是 \(|\Lambda(w)| = \mathcal{O}(\log w)\).

由引理 4 和引理 5，可以简单推出 \(|s_i|\ge 2|s_{i+1}|\)，而满足\(|s_i|\ge 2|s_{i+1}|\) 的串只有 \(\mathcal{O}(\log|w|)\) 个，于是显然.

实际运用中往往不需要求出每个后缀是否为 Significant Suffix，只需取 \(\{s_i\big| |s_i|\ge 2|s_{i+1}|\}\) 即可.

标签：后缀,知识,ge,Lyndon,速记,cdots,引理,Lambda
From： https://www.cnblogs.com/0922-Blog/p/18218119/Lyndon