前言

群除我会了或者即将会了

鸽了 $100$ 年终于来学了。

本学习笔记基本参考【IOI2021 论文集】胡昊,浅谈 $\text{Lyndon}$ 分解。
还有这里

$\text{orz huhao}$

定义

对于字符串 $S$,称其为 $\text{Lyndon}$ 串当且仅当 $S$ 严格 $<$ 其所有后缀。

称字符串 $S$ 的 $\text{Lyndon}$ 分解为:将字符串划分为若干子串 $A_1A_2\cdots A_k$,满足 $\forall i$,$A_i$ 是 $\text{Lyndon}$ 串,且 $A_i\ge A_{i+1}$。

前置证明

$S$ 是 $\text{Lyndon}$ 串 $\iff$ $S$ 是其所有循环同构中字典序严格最小的。

注意上述定义中给出的是严格小于所有后缀证明没太看懂,到时候再补

若 $Sa$ 是某个 $\text{Lyndon}$ 串的前缀,其中 $S$ 是字符串, $a$ 是某个字符;则对于 $b>a$,$Sb$ 是 $\text{Lyndon}$ 串。

对于 $S$ 一个后缀 $T$,有 $Sa<Ta$。考虑两个串第一次不一样的位置 $p$,若在 $|Ta|-1$ 及以前,则不改变大小关系;若恰好是 $|Ta|$,则将 $a$ 替换成 $b$ 也不改变大小关系。

若 $S,T$ 都是 $\text{Lyndon}$ 串且 $S<T$,则 $ST$ 是 $\text{Lyndon}$ 串。

若 $|S|\ge |T|$,则 $ST<T$,又 $S,T$ 分别是 $\text{Lyndon}$ 串,所以所有 $T$ 的后缀都 $> T$。

若 $|S|<|T|$,分类讨论一下。若 $S$ 不是 $T$ 的前缀,则显然 $ST<T$;若 $S$ 是 $T$ 的前缀,考虑反证:若 $ST$ 不是 $\text{Lyndon}$ 串,则 $ST>T$,这说明 $T_{|S|+1...n}<T$,与 $T$ 是 $\text{Lyndon}$ 串矛盾。因此证毕。

$\text{Lyndon}$ 分解存在且唯一。

存在性:

一开始设 $S$ 是 $n$ 个长度为 $1$ 的串 $s_1s_2s_3\cdots s_n$,则每次只需要找两个 $s_i<s_{i+1}$,将其合并为一个部分就行了。

唯一性:

反证,假设存在两种 $\text{Lyndon}$ 分解:

$$ S=A_1 A_2\cdots A_i A_{i+1}\cdots A_k $$

$$ S=A_1 A_2\cdots A_i A'_{i+1}\cdots A'_{k'} $$

不妨设 $|A_{i+1}|<|A'_{i+1}|$。设 $A'_{i+1}=A_{i+1}A_{i+2}\cdots A_{m_{1...p}}$,则:

$$ A'_{i+1}<A_{m_{1...p}}\le A_m<A_{i+1} $$

又 $A_{i+1}$ 是 $A'_{i+1}$ 的前缀,所以矛盾。

一个 $\mathcal{O}(n\log n)$ 的算法

设 $a_i$ 表示 $i$ 之后,第一个位置 $j$ 使得 $S_{i...n}>S_{j...n}$,若不存在,则设 $a_i=n+1$。

则 $S$ 的 $\text{Lyndon}$ 分解的第一项是 $S_{1,a_1-1}$,后面的项就是 $S_{a_1,n}$ 的 $\text{Lyndon}$ 分解。

由于要比较后缀的大小关系,所以需要使用 $\text{Suffix Array}$,复杂度 $\mathcal{O}(n\log n)$。

注意到,此算法可以得到所有后缀的 $\text{Lyndon}$ 分解。

$\text{Duval}$ 算法

$\text{Duval}$ 算法可以在 $\mathcal{O}(n)$ 的时间复杂度内求出一个串的 $\text{Lyndon}$ 分解。其主要思想就是将字符串 $S$ 划分为三部分 $S_1,S_2,S_3$,分别表示已经划分完毕的部分,正在划分的部分,和还未考虑的部分。

其中 $S_2=t^m+v$,其中 $t$ 是一个 $\text{Lyndon}$ 串,$v$ 是 $t$ 的一个前缀。

现在建立三个指针 $i,j,k$,$i$ 指向 $S_2$ 的第一个字符,$k$ 指向 $S_3$ 的第一个字符,$j$ 指向 $k-|t|$,即上一个循环节中 $k$ 的对应位置。

  • 若 $s_k=s_j$,则循环节可以继续延申,$j\leftarrow j+1,k\leftarrow k+1$。
  • 若 $s_k>s_j$,根据上述结论,$v+s_k$ 是一个 $\text{Lyndon}$ 串。由于要满足递减的条件,所以 $v+s_k$ 要一直往前合并,最后会组成 $t^m+v+s_k$ 为一个新的 $\text{Lyndon}$ 串。即 $j\leftarrow i,k\leftarrow k+1$。
  • 若 $s_k<s_j$,则我们称 $t^m$ 的部分的 $\text{Lyndon}$ 分解已经被确定,将 $m$ 个 $t$ 串加入 $S$ 的 $\text{Lyndon}$ 串,从 $v$ 的开头开始继续分解。

注意到,此算法可以得到所有前缀的 $\text{Lyndon}$ 分解。

几个问题

为啥是 $\mathcal{O}(n)$?

$i,k$ 是递增的,$j$ 的移动次数不超过 $k$,故是 $\mathcal{O}(n)$。

为啥这样分解出的 $\text{Lyndon}$ 串字典序不增?

考虑每次从 $S_2$ 中放入 $S_1$ 中需要满足什么条件。首先 $v$ 是 $t$ 的前缀,且最新的字符 $s_k<s_j$,则我们会在 $S_1$ 中放入若干 $t$。由于 $j,k$ 是 $t$ 的对应位置,所以一定有 $v+s_k<t$,故字典序不增。

标签: Lyndon

添加新评论