字符串学习笔记

RoFtaCD / 2023-08-18 / 原文

SAM （后缀自动机）

待补充

Lyndon 分解

定义：

定义一个串是 $\text{Lyndon}$ 串，当且仅当此串的最小后缀为此串本身。

等价于该串为它所有循环表示中字典序最小的。

$\text{Lyndon}$ 分解将任意串 $S$ 划分成字符串序列，满足序列中每个串均为 $\text{Lyndon}$ 串且每个串字典序均大于等于其之后的串。

可以证明这种划分存在且唯一，证明略。

算法：

引理 1：若串 $u$ 和 $v$ 都是 $\text{Lyndon}$ 串且 $u<v$，则 $u+v$ 也是 $\text{Lyndon}$ 串。

证明略。

引理2：若字符串 $u$ 和字符 $c$ 满足 $u+c$ 是某个 $\text{Lyndon}$ 串的前缀，则对于字符 $d>c$ 有 $u+d$ 是 $\text{Lyndon}$ 串。

证明：

设该 $\text{Lyndon}$ 串为 $u+c+t$。

则根据性质就有 $\forall i \in [2,len(u)],u[i:]+c+t>u+c+t$，

也就是说 $u[i:]+c\ge u$，(即为 $u$ 的后缀加上字符 $c$ 后字典序仍比 $u$ 大)。

所以就有 $u[i:]+d>u[i:]+c\ge u$。

同时因为 $c>u[1]$，就有 $d>c>u[1]$。

故 $u+d$ 为 $\text{Lyndon}$ 串。

$\text{Duval}$ 算法:

这个算法可以在 $ \mathcal{O}(n)$ 时间复杂度，$\mathcal{O}(1)$ 空间复杂度内求出一个字符串 $S$ 的 $\text{Lyndon}$ 分解。

维护三个变量 $i,j,k$，$i,k$ 将字符串分为三段。

$S[:i−1]$ 为已经分解好且满足字典序非递增的 $g$ 个 $\text{Lyndon}$ 串。（$s_1s_2s_3 \dots s_g$)

$S[i,k−1]=t^h+v(h>1)$ 尚未分解，满足 $t$ 是 $\text{Lyndon}$ 串，且 $v$ 是 $t$ 的一个可为空且不等于 $t$ 的前缀，且有 $s_g>S[i,k-1]$

程序实现时按顺序读入字符 $S[k]$，令 $j=k-|t|$。

以 $S[j]$ 和 $S[k]$ 为依据分类讨论。

当 $S[k]=S[j]$ 时，直接 $k\leftarrow k+1,j\leftarrow j+1$，尾部字符串 $v$ 的周期 $k-j$ 继续保持
当 $S[k]>S[j]$ 时，由 引理 2 可知 $v+S[k]$ 是 $\text{Lyndon}$ 串，由于 $\text{Lyndon}$ 分解需要满足 $s_i\ge s_{i+1}$，所以继续向前合并，并且最终整个 $t^h+v+S[k]$ 会形成一个新的 $\text{Lyndon}$ 串（所以将 $j$ 调回 $i$ 的位置继续判断）。
当 $S[k]<S[j]$ 时，$t^h$ 的分解被固定下来，算法从 $v$ 的开头处重新开始，之前的都归到 $i$ 前的第一部分。

$i$ 只会单调往右移动，同时 $k$ 每次移动的距离不会超过 $i$ 移动的距离，所以时间复杂度是 $ \mathcal{O}(n)$ 的。

核心代码：

for(int i=1;i<=n;){
	int j=i,k=i+1;
	while(k<=n && s[k]>=s[j]){ //前两种情况
		if(s[k]>s[j]) j=i;
		else ++j;
		++k;
	}
	while(i<=j){
        // 在此处获取字串信息
        // 每个字串的长度均为 k-j
		i+=k-j;
	}
}

一个子串的左端点为 $i$，右端点为 $i+k-j-1$。

未完待续