Lyndon Word 入门
FLY_lai
·
·
算法·理论
【定义与性质】
Primitive Word（PW）：没有循环节的字符串。
Lyndon Word（LW）：字典序严格小于它所有 cyclic-shift 的字符串。
LW 有很多美妙的性质。记 w 为一个字符串。
定义一个新符号 <_!：若 a<_!b，则 a 字典序小于 b 且 a 不是 b 的前缀。
1. $w\in LW\iff$ $w$ 严格小于 $w$ 所有 cyclic-shift。这是定义。
1. 若 $w\in LW$，则 $w$ 无 border。
若 $w=uvu$，则 $w=xu=uy$，则 $w=uy<ux$（$w$ 小于所有 cyclic-shift）。
$\because uy<ux\therefore y<x$，同理可知 $x<y$。矛盾。
所以 $w$ 无 border。
1. 等价定义：$w\in LW\iff w$ 小于所有真后缀。
记 $w$ 的一个后缀为 $v$，$w=uv$。
若 $uv\in LW$，反证法，如果 $uv>v$，因为 $uv$ 无 border，所以 $uv>_!v$，则 $uv>vu$，与 $uv\in LW$ 矛盾。
若 $uv<v$，有 $uv<v<vu$。
证毕。
1. 等价定义：$w\in LW\iff$ 将 $w$ 任意拆成 $w=uv$，$u<v$。（$u,v$ 非空）
换句话说就是 $w$ 的前缀小于后缀。
$\Leftarrow$：证 $uv<vu$。若 $u<_!v$，显然；否则 $u$ 是 $v$ 的前缀。
设 $v=u^kr$，其中 $|r|<|u|$。则 $w=u^{k+1}r$。因为前缀小于后缀，$u^{k+1}<r$，所以 $u<_!r$。（注意 $|r|<|u|$ 不可能是前缀）
而 $uv=u^{k+1}v,vu=u^kru$，显然有 $vu>uv$。
$\Rightarrow$：$w\in LW$。那么 $w$ 小于每个真后缀。
则 $w=uv$，有 $u<uv<v$。（第一个 $<$ 是前缀关系，第二个是真后缀）
1. 记 $u,v\in LW$。$uv\in LW\iff u<v$。
$\Rightarrow$：由上面的等价定义直接推出。
$\Leftarrow$：尝试用 "小于每个真后缀" 证明。
把所有真后缀 $suf$ 分类：$v$ 是 $suf$ 真后缀的、$suf=v$、$suf$ 是 $v$ 真后缀。
1. $v$ 是 $suf$ 真后缀的。则 $suf$ 可以写成 $u'v$ 的形式。$u'$ 是 $u$ 的真后缀。
因为 $u\in LW$，所以 $u$ 没有 border 且 $u<u'$，所以 $u<_!u'$，所以 $uv<u'v$。
1. $suf=v$。若 $u<_!v$，显然成立；否则 $u$ 是 $v$ 的前缀，设 $v=uv'$。因为 $v\in LW$，所以 $v<v'$，（同时加 $u$）所以 $uv<uv'=v$，得证。
1. $suf$ 是 $v$ 的真后缀。$uv<v<suf$。
证毕。
1. LW 的标准分解定理。若 $w\in LW$，取 $w$ 的最小真后缀 $v$，则 $v$ 是 $w$ 的最长 $LW$ 真后缀，且（记 $w=uv$） $u,v\in LW$。
证明：
若存在 $sv\in LW$。因为 $sv\in LW$，知 $sv<v$，我们就得到了一个比最小真后缀更小的真后缀，矛盾。
因为 $v$ 是最小真后缀，所以 $v$ 小于所有 $v$ 的真后缀，所以 $v\in LW$。
因为 $uv\in LW$，所以对于任意 $u$ 的后缀 $u'$，有 $uv<u'v$。因为 $|u|>|u'|$，所以 $u<u'$，所以 $u\in LW$。
1. 由 6 引申出一个 $LW$ 的递归定义法，就是每个长度 $>1$ 的 $LW$ 都能拆成两个 $LW$。
# 【Lyndon 分解】
定理：每一个字符串 $s$ 都能**唯一表示**为 $s=w_1w_2\cdots w_k$，满足 $w_i\in LW$ 且 $w_i\ge w_{i+1}$。
存在性：
先把 $s$ 拆成 $n$ 个单字符（显然单个字符是 $LW$），然后只要有两个相邻的前面 $<$ 后面，就合并。这么做是对的，理由来自上面性质的第五点。把 $<$ 都合并了就余下 $\ge$ 了。
唯一性：
反证法。考虑两种方案 $S,S'$，假设 $S_i$、$S'_i$ 是第一处不相同的分解位置。
不妨 $|S_i|>|S'_i|$。记 $S_i=S'_iS'_{i+1}\cdots S'_{k-1}Pre(S'_k,t)$，就是一堆整的加一个前缀。要求 $k>i$。
因为 $S_i\in LW$ 且 $Pre(S'_k,t)$ 是它的一个后缀，所以 $Pre(S'_k,t)>S_i$。
因为 $S'_i$ 是 $S_i$ 的前缀，所以 $S_i>S'_i$。
所以 $Pre(S'_k,t)>S_i>S'_i\ge S'_{i+1}\ge\cdots\ge S'_{k-1}\ge S'_k$。于是得到了 $Pre(S'_k,t)>S'_k$，前缀大于本身，矛盾。
------
Lyndon 分解有它美妙的性质。记 $CFL(w)=w_1\cdotsw_m$ 为 $w$ 的 Lyndon 分解。
1. $w_m$ 是最小后缀。
考虑 $w$ 的一个后缀 $v$，如果 $v$ 是 $w_m$ 的后缀，因为 $w_m\in LW$，所以 $w_m$ 会比它更小。
而当 $v=w_i'w_{i+1}w_{i+2}\cdots w_m$，其中 $w_i'$ 是 $w_i$ 的一个后缀。$v>w_i'\ge w_i\ge w_{i+1}\ge\cdots\ge w_m$。
2. $w_m$ 是最长的 $LW$ 后缀。
$w_m$ 是最小后缀，所以任意比 $w_m$ 长的后缀都有 $w_m$ 这个更小的真后缀，非 $LW$。
3. $w_1$ 是最长 $LW$ 前缀。
记 $s=w_1w_2\cdots w_k'$，$w_k'$ 是 $w_k$ 的前缀。则 $s> w_1\ge w_2\ge\cdots\ge w_k\ge w_k'$，于是 $s$ 有了一个更小的后缀。
## 【Duval 算法求 Lyndon 分解】
- 定义：准 $LW$。若 $t=w^kw'$，且 $w\in LW$，$w'$ 是 $w$ 的前缀，则 $t$ 是准 $LW$。
容易发现，准 $LW$ 就是 $LW$ 的前缀。
引理：两字符 $c<c'$。若 $vc$ 是准 $LW$，则 $vc'$ 是 $LW$。
证明：$vc$ 是准 $LW$，记 $vcu$ 是 $LW$。有 $vcu$ 任意一个前缀 $<$ 后缀。考虑 $v$ 的一个前缀 $a$，$a<(v-a)cu<(v-a)c'$，所以 $vc'$ 的任意一个前缀也 $<$ 后缀。
------
Duval 算法是一个能 $O(|w|)$ 求出 $w$ 的 Lyndon 分解的算法。
在算法过程中，我们把字符串 $w$ 分成四类：已经输出的、连续相同的 $LW$、$LW$ 的前缀、未处理部分。
黑色部分是已经输出的 $s_1\sim s_g$，要求 $s_1\ge s_2\ge\cdots\ge s_g$。
蓝色部分是正在处理，尚未确定的部分。$t_1\sim t_h$ 都相等，$v$ 是 $t_i$ 的前缀。可以把 $t_1t_2\cdots t_hv$ 看作一个准 $LW$。
红色部分是尚未处理的。
然后我们维护三个指针 $i,j,k$。$i$ 指向蓝色部分的开头，$k$ 指向下一个要处理的字符，$j$ 指向 $k-|t_i|$（可以理解为若还想保持 $t_i$ 不变，$k$ 指向的字符应该和 $j$ 指向的字符相同）。
1. $w_k=w_j$。若 $v$ 已经等于 $t_i$ 了，新开一个 $v$；否则往 $v$ 里加就好。
2. $w_k>w_j$。把 $t_1t_2\cdots t_hvw_k$ 一起作为一个新的 $t_1$。
3. $w_k<w_j$。输出 $t_1\sim t_h$（变成 $s$ 部分），**令 $k$ 指向 $v$ 开头重新跑**。
若 $k$ 已经指向结尾之后，但是 $v$ 非空，把 $k$ 指向 $v$ 开头重新跑。
代码很短。
<details>
<summary>点击查看代码</summary>
```
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int i, j, k;
int main() {
int ans = 0;
cin >> s;
n = s.size();
s = ' ' + s;
i = 1;
while (i <= n) {
j = i;
k = i + 1;
while (s[k] >= s[j]) {
if (s[k] == s[j])
j++;
else
j = i;
k++;
}
while (i <= j) {
ans ^= (i + (k - j) - 1);
i += k - j;
}
}
cout << ans << endl;
return 0;
}
```
</details>
## 【Lyndon 分解的各种应用】
### 求字符串的最小表示法
若对 $s$ 求最小表示法，令 $s'=ss$。$CFL(s')$ 中包含 $s'_n$ 的 LW 开始位置，就是 $s$ 最小表示法的开始位置之一。
引理：设 $CFL(w)=w_1\cdots w_m$。$w_i=w[L_i,R_i]$。则以 $[1,R_i]$ 作为起点的后缀中，以 $L_i$ 为起点的是最小的。
证明：考虑起点 $x\neq L_i$。
1. $L_i<x\le R_i$。因为 $w_i\in LW$，所以 $w_i<w[x,R_i]$，所以 $w_i<_!w[x,R_i]$（长度更长还小）。所以 $suf(L_i)<suf(x)$。
1. $x<L_i$，设 $x\in [L_j,R_j]$，$w_j'=w[x,R_j]$。
有 $w_j'\ge w_j\ge w_{j+1}\ge\cdots\ge w_i$，所以 $w_i\le w_j'$。
若 $w_i<_! w_j'$，显然；否则 $w_i$ 是 $w_j'$ 的前缀。
那么比 $suf(x),suf(L_i)$ 其实就是比 $suf(x+R_i-L_i+1),suf(L_{i+1})$。
如此循环下去，可以用归纳法到 $suf(x+?),suf(L_m)$，而 $w_m$ 是最小后缀。
证完引理，回到原来的算法。在 $s'$ 中，最小表示法就是 $s'$ 的一个长度为 $|s|$ 的子串。
要比较它们，也相当于比较对应开始位置在 $s'$ 里的后缀的大小关系。最小者，肯定前 $|s|$ 个字符也是最小的。
### Lyndon Word 生成算法/找后继
> 记 $|\sum|=k$。要求按照字典序从小到大生成所有长度 $\le n$，字符集大小为 $k$ 的 LW。
把字符集看作 $k$ 进制数。最小的 LW 显然是 $0$。如果我们能找某个 LW 的后继，就可以从 $0$ 生成所有的了。
而可以找到 $w\in LW$ 的后继。这么做：
1. 截取 $R(w)$ 的前 $n$ 个字符，记为 $w'$。（例如 $n=3,w=01,w'=010$）
2. 删除 $w'$ 末尾连续的最大字符。（例如 $w'=012,k=3$，删完之后 $w'=01$）
3. $w'+1$，就是 $k$ 进制数意义下的。因为已经删完了末尾的最大字符，所以肯定不会进位。
例如 $\sum = \{0,1,2\},n=3$，可以生成出：$0,001,002,01,011,012,02,021,022,1,112,12,122,2$。
### LW 计数
> 求 $len\le n,|\sum|=k$ 的 LW 个数。
可以等价到另外一个问题：项链计数，要求没有循环节，称这个为问题 1。
考虑问题 2：项链计数，允许有循环节。
记问题 1 的答案为 $S_n$，问题 2 的答案为 $T_n$。（$k$ 是固定的）
考虑集合 $A$ 包含所有 $n$ 个珠子的项链，显然 $|A|=k^n$。
考虑集合 $B$（多重集）包含 $T_n$ 里所有项链的 cyclic-shift。
$B$ 的大小比 $A$ 大，因为有的项链重复出现了。（例如 $0101$ 出现两次）
同时 $|B|=n\cdot T_n$。
考虑算 $|B|$。用 $A$ 中每个元素在 $B$ 出现次数之和除以 $n$ 可得 $T_n$。记 $S$ 为出现次数之和
$$\begin{aligned}
S&=\sum_{(a_0,\dots,a_{n-1})\in A}\sum_{i=0}^{n-1}[a_0a_1\cdots a_{n-1}=a_i\cdots a_{n-1}a_0\cdots a_{i-1}]\\
&=\sum_{i=0}^{n-1}\sum_{(a_0,\dots,a_{n-1})\in A}[\cdots]\\
&=\sum_{i=0}^{n-1}k^{gcd(n,i)} \text{ (相当于枚举循环节长度)}\\
&=\sum_{d\mid n}\varphi(d)\cdot k^{\frac{n}{d}}\\
\end{aligned}
$$
所以 $T_n=\dfrac{1}{n}\sum_{d\mid n}\varphi(d)\cdot k^{\frac{n}{d}}$。另外 $T_n=\sum_{d\mid n}S_d$，即枚举循环节。
推导一下。记 $K(x)=k^x$.
$$T_n=\dfrac{1}{n}\sum_{d\mid n}\varphi(d)\cdot k^{\frac{n}{d}}\Rightarrow n\cdot T_n=\varphi * K\Rightarrow n\cdot T=id*\mu *K$$
同时 $T_n=\sum_{d\mid n}S_d\Rightarrow n\cdot T=n(S*1)$。
**待证明**：经过一些运算，$n\cdot T=id*(nS)$。
所以 $n\cdot T=id*\mu*K=id*(nS)$，所以 $nS=\mu * K$，所以 $S_n=\dfrac{1}{n}\sum{d\mid n}\mu(d)\cdot k^{\frac{n}{d}}$。
## 【利用 Duval 算法中间结果】
在跑 Duval 的过程中同步计算答案。
### 求每个前缀的最小后缀
记 $ans[i]$ 为 $w[1\sim i]$ 最小后缀开始位置。
1. $w[k]=w[j]$，则 $ans[k]=ans[j]+(k-j)$。可以类比着来看。
2. $w[k]>w[j]$，$ans[k]=i$。
3. $w[k]<w[j]$，这种情况不管，因为 $k$ 回溯之后会处理的。