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\)。

未完待续