Lyndon Word 小记

rlc202204 / 2024-08-04 / 原文

1. 定义

一个字符串 $S$ 被定义为 Lyndon Word 当且仅当其严格小于所有真 cyclic shift。

Lyndon Word 的等价定义：是其所有后缀中最小的。

2. 性质

性质 1： Lyndon Word 无 $\text{Border}$。

不妨设 $w$ 有 $\text{Border}$，则我们可以表示为 $w = xu = uy$，从而得到 $w < ux, w < uy$，替换一下得到 $y < x$ 和 $x < y$，显然矛盾。

性质 2： $u, v$ 都是 Lyndon Word，则 $uv$ 是 Lyndon Word $\iff u < v$。

如果 $uv$ 是 Lyndon Word，则我们得到 $uv < v$，同时 $u < uv$，所以 $u < v$。

我们分情况考虑三种后缀。

第一种，$s = u'v$我们知道 $u < u'$，因为 $|u| > |u'|$，所以加上 $v$ 依然成立。

第二种 $v$，我们考虑证明 $uv < v$，按照长度来，如果 $u > v$ 显然成立，否则若 $u$ 为 $v$ 的前缀，不妨设 $v = uv'$，我们已知 $v < v'$，所以 $uv < uv'$ 得证。

第三种比 $v$ 还小的可以从第二种直接看出来。

性质 3： $w$ 是 Lyndon Word $\iff \forall w = uv$，$u < v$（$u, v$ 非空）

从左边往右，我们知道 $uv < v$ 和 $u < uv$ 即可推出。

反过来，我们需要证明 $uv < vu$，这是根据定义来证明，分两种情况。

我们设 $a<_!b$ 表示 $a$ 小于 $b$ 且不是 $b$ 的前缀。

如果 $u<_!v$，则不难推出 $uv < vu$。否则，我们设 $v = u^kr$，其中 $u$ 不是 $r$ 的前缀。

由于 $w = uv = u^{k+1}r$，得到 $u^{k+1} < r$ 从而 $u < r$，于是 $u <_! r$ 最终得到 $ur < ru$。

所以我们有 $uv = u^{k} u r > u^{k}ru = vu$，得证。

性质 4（标准分解）： $w$ 是 Lyndon Word，取最小真后缀 $v$，假设 $w = uv$，则：$u,v$ 也是 Lyndon Word 且 $u < v$，并且 $v$ 是 $w$ 的最长 Lyndon Word 真后缀。

由于 $v$ 是最小真后缀，所以显然 $v$ 是 Lyndon Word，而 $u$ 的所有后缀 $u'$ 均满足 $uv < u'v$，由于 $|u| > |u'|$，说明 $u$ 一定小于 $u'$。

递归定义： $w$ 是 Lyndon Word 当且仅当 $|w| = 1$ 或存在 $w = uv, u < v$ 且 $u, v$ 是 Lyndon Word。

递归定义是性质 4 的推论。

3. Lyndon 分解

重头戏来了。

将任意字符串 $s$ 分解为若干 Lyndon Word $t_1t_2\dots t_m$，满足 $t_1 \ge t_2 \ge t_3 \ge \dots \ge t_m$，称作 Lyndon 分解。

性质 5： Lyndon 分解存在且唯一。

其实很简单，我们考虑先都分成单个字符，然后只要有 $s_i < s_{i+1}$ 我们就合并，根据性质 2 得到的依然是 Lyndon Word，所以肯定存在。

再考虑唯一性，我们反证法，假设不唯一，存在一个 $t_i = t'_it'_{i+1}\dots t'_{k}pre(t'_{k+1})$，我们能够推出 $t_i < pre(t'_{k+1})\le t'_{k+1} \le t'_{i}$，但是前缀关系使得 $t'_i < t_i$，矛盾！所以得证。

我们一般将 $s$ 的 Lyndon 分解称作 $\text{CFL(s)}$。

性质 6： $\text{CFL(w)} = w_1w_2\dots w_m$，那么：

$w_m$ 是 $w$ 的最小后缀。
$w_m$ 是最长的 Lyndon Word 后缀。
$w_1$ 是最长的 Lyndon Word 前缀。

证明：

我们考虑任何一个后缀 $s = suf(w_i)w_{i+1}\dots w_{m}$，能得到 $s \ge suf(w_i) \ge w_{i + 1} \ge \dots w_m$，所以 $\forall s, w_m \le s$。
上面的证明中设 $s$ 严格长于 $w_m$，则 $i < m$, $suf(w_i) < s, w_m < s$，从而推出 $s$ 不是 Lyndon Word。
设 $T = w_1w_2\dots w_ipre(w_{i+1})$，则 $pre(w_{i+1}) \le w_{i+1} \le w_{i} \le \dots \le w_1 \le T$，所以 $pre(w_{i+1}) \le T$，不是 Lyndon Word。

性质7： 设 $\text{CFL(w)} = w_1w_2\dots w_m$ 其中 $w_i$ 的位置是 $[l_i, r_i]$，则所有 $[1,r_i]$ 开始的后缀中，$l_i$ 开始的是最小的。

对于 $x > l_i$，很容易证明 $suf(x) > suf(l_i)$。

否则，我们设 $suf(x) = w'_{j}w_{j+1}\dots w_m$，所以 $w_i \le w_j \le w'_j$。

如果 $w_i <_!w'_j$，则可以证明 $suf(x) > suf(l_i)$，否则 $w_i$ 是 $w'_j$ 前缀，我们可以归纳证明，已经证明了 $w_{i + 1} < w'_{j+1}$，然后就能证明 $suf(x) > suf(l_i)$ 了。

4. Duval 算法

这个算法可以用来求 Lyndon 分解。

我们称 $t = w^kw'$ 为准 Lyndon Word 当且仅当 $w'$ 是 $w$ 的前缀并且 $w$ 是 Lyndon Word。

性质 8： $c < c'$（字符），$vc$ 是某个 Lyndon Word 的前缀 $\to$ $vc'$ 是 Lyndon Word。

假设 $vcu$ 是 Lyndon Word，那么 $v$ 的任何一个后缀加上 $c'$ 肯定要大于 $vc'$，所以得证了。

我们开始描述这个算法流程。这是一个增量算法。

不妨假设现在我们已经固定了 $s_1 \dots s_y$，后面是若干个 $t$ 和一个 $t'$ 满足 $t'$ 是 $t$ 的前缀。

现在 $i$ 等于第一个 $t$ 开始的位置，$j,k$ 是当前的比较，满足 $j = k + |t| - 1$。

然后是过程：

如果 $w_k = w_j$，则 $k,j$ 都增大 1。
如果 $w_k > w_j$，则合并所有的 $t$ 和 $t'$ 和 $w_k$，根据引理，这个串是 Lyndon Word，所以成为新的 $t$。
如果 $w_k < w_j$，我们将所有的 $t$ 固定下来，然后将算法回到 $t'$ 开始的位置重新开始。

考虑到每次 $k$ 往回退 $i$ 至少往前移相同距离，所以时间复杂度是 $O(n)$ 的。

P6114 【模板】Lyndon 分解

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
string s;
int n;
int main() {
	cin >> s;
	n = (int)s.size();
	s = "=" + s;
	int i = 1, j = 0, k = 0;
	int ans = 0;
	while (i <= n) {
		j = i;
		k = i + 1;
		while (k <= n && s[k] >= s[j]) {
			if (s[j] < s[k])
				j = i;
			else
				j++;
			k++;
		}
		while (i <= j) {
			ans ^= (i + (k - j) - 1);
			i += (k - j); 
		}
	}	
	cout << ans << endl;
	return 0;
}