学习笔记 - Lyndon分解 | Lucky_Glass's Blog
0%

学习笔记 - Lyndon分解

打多校赛学新算法的日常 QwQ


# Lyndon 串

Lyndon 串的标准定义是:若字符串 $S$ 满足其本身的字典序严格小于其任何一个真后缀,则称 $S$ 是 Lyndon 串。

这个定义等价于 $S$ 本身是所有 $S$ 的循环同构串中字典序唯一最小的一个串。

Tab. 以下用 $S[i:]$ 表示 $S$ 从 $i$ 开始的后缀,$S[:i]$ 表示前缀;“$<$” 表示字典序小于

点击展开/折叠等价证明

考虑 $T_i$ 是以 $S$ 的第 $i$ 位为起点的循环同构串。

首先证明必要性:因为 $S< S[i:]$,又有 $S[i:]$ 是 $T_i$ 的前缀,故 $S< T_i$ 对于任意 $i\neq 1$ 成立。

然后证明充分性:$T_i$ 以 $S[i:]$ 为一个前缀,则一定有 $S[i:]\ge S$($i\neq1$),下面证明不可能为 $S[i:]=S$;
$T_i$ 分解为 $T_i=S[i:]+S[:i-1]$,如果 $S[i:]=S[:n-i+1]$,则有 $S>S[:i-1]>S[n-i+2:]$,矛盾。所以一定是 $S[i:]>S$。


# Lyndon 分解

一个字符串 $S$ 可以唯一分解成 $S=t_1+t_2+\dots+t_m$,其中 $t_i$ 是 Lyndon 串,且满足 $t_1\ge t_2\ge\dots\ge t_k$。

引理1

如果 $u,v$ 均为 Lyndon 串且 $u< v$,则 $u+v$ 是 Lyndon 串。

证明一下。

首先因为 $u$ 是 Lyndon 串,$u[i:]>u$,则也有 $u[i:]+v>u+v$。

然后证明 $v>u+v$,还得分两类:

  1. $u$ 是 $v$ 的前缀:设 $u$ 的长度为 $d$,则 $v=v[:d]+v[d+1:]$,因为 $u=v[:d]$,又因为 $v[d+1:]>v$,所以 $v[:d]+v[d+1:]>u+v$,即 $v>u+v$;
  2. $u$ 不是 $v$ 的前缀,即存在 $i$ 使得 $u[:i]=v[:i]$ 且 $u_{i+1}< v_{i+1}$;显然也有 $(u+v)[:i]=v[:i]$ 且 $(u+v)_{i+1}< v_{i+1}$,则 $v>u+v$;

然后我们就可以继续证明 Lyndon 分解的存在性和唯一性了。

点击展开/折叠存在性的证明

单个字符一定是 Lyndon 串,初始时有 $len$ 个 Lyndon 串;然后每次取相邻的两个 Lyndon 串,若前者小于后者,则可以合并。

点击展开/折叠唯一性的证明

考虑两种不一样的分解 $S=a_1+a_2+\dots+a_p=b_1+b_2+\dots+b_q$。

设 $i$ 是第一个 $a_i\neq b_i$ 的位置,不妨设 $|a_i|>|b_i|$,令 $a_i=b_i+b_{i+1}+\dots+b_{j}[:k]$:

  • $a_i$ 是 Lyndon 串,小于其后缀 $b_{k}[:k]$;
  • $\{b_i\}$ 是 Lyndon 分解,有 $b_i\ge b_j\ge b_j[:k]$;
  • $a_i$ 的前缀 $b_i$ 一定小于 $a_i$。

不等式关系存在矛盾,所以不成立。


# 构造 Lyndon 分解

- 从后缀开始构造

基于引理1。我们用栈储存后缀 $S[i+1:]$ 的 Lyndon 分解,然后加入 $S_i$。

$S_i$ 本身作为一个 Lyndon 串,设当前从 $S_i$ 开始的 Lyndon 串为 $now$,初始时 $now=S_i$。

若栈顶 $top>now$,则可以把 $top$ 接在 $now$ 后面得到新的 $now$ 然后把栈顶 pop 掉。

总共只会合并 $O(n)$ 次,复杂度 $O(nT)$,$T$ 为比较字符串大小的复杂度(只会在合并的时候比较),用SA或者SAM都可以做到 $T=\log n$。

- Duval算法

一个 $O(n)$ 的优秀算法。

引理2

若字符串 $v$ 和 $c$ 满足 $v+c$ 可以是 Lyndon 串的前缀,则对于 $d>c$,$v+d$ 是 Lyndon 串。

简单证明一下,因为 $(v+c)$ 是 Lyndon 串的前缀,则有 $(v+c)[i:]\ge(v+c)[:n-i+1]$($i>1$)。

又有 $(v+d)[i:]>(v+c)[i:]\ge(v+c)[:n-i+1]$,所以 $(v+d)[i:]>(v+c)[:n-i+1]+(v+d)[n-i+2:]$。

也即 $(v+d)[i:]>v+d$($i>1$)。

所以 $v+d$ 是 Lyndon 串。

Duval 算法的主要思想:维护原串的一个分割 $S=T_1+T_2+T_3$:

  • $T_1$ 已经求出了 Lyndon 分解;
  • $T_2=w+w+\dots+w+w[:k]$,其中 $w$ 是 Lyndon 串;
  • $T_3$ 没有进行处理。

每次取出 $T_3$ 的首字符 $c$,加入 $T_2$:

  • 若 $w_{k}=c$,则直接把 $c$ 插入 $T_2$,不会破坏 $T_2$ 的性质;
  • 若 $w_{k}< c$,因为 $w[:k]+w_k$ 是 Lyndon 串的前缀,$w[:k]+c$ 是 Lyndon 串;
  • 若 $w_k>c$,破坏了 $T_2$ 的性质,于是此时 $T_2$ 中所有完整的 $w$ 都是已经确定的 Lyndon 分解,把这些 $w$ 加入 $T_1$,而把剩下的 $w[:k]+c$ 作为 $T_2$。

直到 $T_3$ 为空,根据 Lyndon 分解的存在性定理,最后一定可以构造出一个 Lyndon 分解。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=5e6+10;

int n,ans;
char str[N];

int main(){
scanf("%s",str+1);
n=strlen(str+1);
for(int i=1,j,k;i<=n;){
j=i,k=i+1;
while(k<=n && str[j]<=str[k])
if(str[j]==str[k]) j++,k++;
else j=i,k++;
int len=k-j;
while(i<=j){
ans^=i+len-1;
i+=len;
}
}
printf("%d\n",ans);
return 0;
}


THE END

Thanks for reading!

> Linked 旁观者S的独白-网易云