SAM 学习笔记 & 复杂度证明 & 例题

· · 算法·理论

更多柚子好的阅读体验。

复杂度证明仙人最新力作\qiang，有伪证麻烦评论反馈/kel

复杂度相关证明都在第 4 章。

1 定义

字符串 S 的 SAM 满足：

例如 abbb 的 SAM 如下（绿色表示终止状态）：

注意到如果我们不走到终止状态，本质上是走了一条后缀的前缀也就是一个子串，也就是说从 SAM 的源点可以走出 S 的所有子串。

如果你对 S 的所有后缀建立 AC 自动机，实际上可以做到相似的效果， 但是它会有 O(n^2) 个节点。

对于上图的例子，在 AC 自动机中我们会让 bbb 和 abbb 导向不同的节点，而 SAM 却巧妙地将它们的状态合并了。

本质上，SAM 实际就是将状态充分合并的 AC 自动机。

2 状态信息

2.1 结束位置集合 endpos

2.1.1 定义与 endpos 等价类

结束位置集合 \text{endpos} 指出了 SAM 节点可以合并的条件。

对于字符串 s 的子串 t，记 \text{endpos}(t) 为 t 在 s 中结束位置的集合，例如对于 bangbangt，有 \text{endpos}(\texttt{bang})=\{3,7\}（从零开始编号）。

仔细观察还会发现 \texttt{ang} 和子串 \texttt{bang} 的结束位置集合完全相同，我们将 \text{endpos} 相同的子串划分为同一个等价类。

实际上，SAM 中的每个节点就对应着一个等价类，下文我们将基于此进行构建。

2.1.2 引理与证明

这些引理能理解就不用看证明了，证明都很简单而且没啥用😶。

  1. 引理：若子串 u 和 v 处于同一等价类（|u|\ge|v|），那么 v 每次出现都是 u 的后缀。

    证明：这真显然吧，看不懂的自己摸几个串🤫。

  2. 引理：对于子串 u 和 v （|u|\ge|v|），有：

    \begin{cases} \text{endpos}(u) \subseteq \text{endpos}(v), & \text{if } v \text{ is a suffix of } u\\ \text{endpos}(u) \cap \text{endpos}(v) = \varnothing, & \text{otherwise.} \end{cases}

    证明：如果 u 和 v 的 \text{endpos} 有交，那么考虑结尾相同的位置，显然 v 一定是 u 的后缀，而当 v 是 u 的后缀时，所有 u 出现的位置 v 一定出现，得证。

  3. 引理：对于同一等价类的任意两子串，较短者为较长者的后缀，且该等价类中的子串长度是连续且不重复的。

    证明：由引理 1 可知等价类中子串长度都不重复且较短者为较长者的后缀，接着考虑等价类中最长和最短的两个串，对于长度在它们之间的最长串的后缀，显然也会出现在等价类中（比它更短的最短串都只能以最长串的后缀形式出现）。

2.2 后缀链接 link

2.2.1 定义

定义一个状态的 \text{link} 指向状态所表示等价类中，最长串的不在等价类中的最长后缀所在的状态。

特别地，下文规定源点 t_0 等价类中只有空串，\text{endpos}(t_0)=\{-1,0\cdots |S|-1\}。

2.2.2 引理与证明

和 2.1.2 一样，引理能理解就不用看证明了🤐。

  1. 引理：所有后缀链接构成一颗根节点为 t_0 的树。

    证明：每次跳后缀链接必然会到达对应字符串更短的节点，所以不会有环而且所有节点最后都能跳到空串 t_0 上。

  2. 引理：以 \text{endpos} 集合为节点，集合的包含关系为边所构造的树与 \text{link} 树相同。

    证明：由于实际上 \text{link} 指向的是最长串的后缀，由 2.1.2 的引理 2 有：

    \text{endpos}(u) \subsetneq \text{endpos}(\text{link}(u))

2.3 小结

以字符串 \texttt{abcbc} 为例，让我们对上文的状态进行进一步的认识：

也就是说，对于 SAM，我们有两种理解方式：

在下文对于一个状态 x，我们记 \text{str}(x) 为等价类中最长的字符串，\text{len}(x) 为它的长度，后缀路径默认为它跳 \text{link} 到源点经过的状态，\text{P}(x) 为后缀路径，|\text{P}(x)| 为后缀路径长度。

特别地，规定 \text{len}(t_0)=0，\text{link}(t_0)=-1。

3 构建

3.1 构建过程

SAM 与大多数自动机一样同样采用增量构建方法，下文介绍当 s\leftarrow s+c 时我们要干什么。

贴张 OI-wiki 的图，其中 p_0=last。

这是上面图片加入 c 后的状态，不知道能不能助于你们理解：

3.2 代码

struct{
    int link,len,son[26];
}sam[2001000];
int lst,tot;
void init(){//初始化，代码里我将上面的标号整体 +1 以防止 RE
    lst=tot=1;
    memset(sam,0,sizeof sam);
    sam[1].link=0;
}
void insert(int ch){
    sam[++tot].len=sam[lst].len+1;
    siz[tot]=1;
    int pos=lst;
    lst=tot;
    while(pos!=0&&!sam[pos].son[ch]){//找 p & 新建转移
        sam[pos].son[ch]=tot;
        pos=sam[pos].link;
    }
    if(pos==0){//情况 1
        sam[tot].link=1;
        return;
    }
    int p=pos,q=sam[pos].son[ch];
    if(sam[p].len+1==sam[q].len){//情况 2
        sam[tot].link=q;
    }
    else{//情况 3
        sam[++tot]=sam[q];//复制转移
        sam[tot].len=sam[p].len+1;
        sam[tot-1].link=sam[q].link=tot;
        while(pos!=0&&sam[pos].son[ch]==q){//重定向转移
            sam[pos].son[ch]=tot;
            pos=sam[pos].link;
        }
    }
}

4 相关证明

4.1 状态数与转移数

这个部分有更紧的上界但是变化量 O(1)，这里不做赘述，因为确实没啥用😕。

结论：SAM 的状态数至多为 2n，转移数至多为 3n。

4.2 复杂度证明

下文的分析建立在操作后的 SAM 上。

综上，SAM 的总构建复杂度是线性的。

5 例题

[SDOI2016] 生成魔咒

题目大意

给定一个字符串，求在每次加入节点后的本质不同子串个数。

题解

考虑每次加入新点后字符串增加的本质不同子串个数，我们发现实际上就是 cur 所表示 \text{endpos} 集合的大小，这个东西可以用 \text{len}(cur)-\text{len}(\text{link(cur)}) 轻松计算。

[TJOI2015] 弦论

题目大意

给定一个长度为 n 的字符串，求相同子串算作/不算作同一个时的第 k 小子串。

题解

相同子串不算做同一个无非就是让每个串都对排名产生出现次数次贡献，出现次数考虑对于状态 u，它的出现次数等于所有 \text{link} 为它的状态的出现次数和，（由 \text{endpos} 的性质可知，这些状态的 \text{endpos} 都没有交，u 作为它们的后缀出现统计显然不重不漏），边界条件是所有的原串前缀出现次数初始为 1（当然这不意味着它们不能从后缀链接转移）。

为保证复杂度，我们需要记录走入一个状态内要消耗多少排名，dfs 时优先走最小的转移，模仿平衡树第 k 小写就行了。

[AHOI2013] 差异

题目大意

给定一个长度为 n 的字符串 S，令 T_i 表示它从第 i 个字符开始的后缀。求

\displaystyle\sum_{1\leqslant i<j\leqslant n}\operatorname{len}(T_i)+\operatorname{len}(T_j)-2\times\operatorname{lcp}(T_i,T_j)

其中，\text{len}(a) 表示字符串 a 的长度，\text{lcp}(a,b) 表示字符串 a 和字符串 b 的最长公共前缀。

题解

首先这个 \text{len} 可以轻松提出来求解，每个前缀都会被计算 n-1 次。

=\frac{(n-1)n(n+1)}{2}-2\displaystyle\sum_{1\leqslant i<j\leqslant n}\operatorname{lcp}(T_i,T_j)

考虑 \text{lcp} 怎么求，由于这是 SAM 学习笔记所以把我们的 SA 收起来，SAM 并不好处理前缀信息，考虑反着建 SAM，问题变为求两两前缀最长公共后缀的和。

考虑在 \text{fail} 树上对每个状态作为公共后缀统计答案，令 sum_i 表示 i 子树内有多少前缀，S 为 i 的儿子集合，有：

ans=\sum_{i=1}^{id}\text{len}_i\sum_{j\in S} sum_j(sum_i-sum_j)

原因意会，感觉比较显然。

[NOI2018] 你的名字

噔噔咚。

题目大意

给定一个模版 S，多组询问，每次给出询问字符串 T 和区间 [l,r]，求输出 T 的本质不同子串满足没有在 S 的 [l,r] 区间内出现。

题解

首先我们将问题转化为 T 的本质不同子串减去出现过的个数，前者是例题 1，下面讲解后者。

先考虑 l=1,r=|S| 怎么做：

直接对 S 和 T 都建出 SAM，正常匹配本质不同公共子串，但是同时维护 T 的对应节点，当该节点的匹配长度为 k 时，这意味着等价类中长度 \le k 的后缀都会匹配上，该节点的贡献为 \max(k-\text{len}(\text{link}(p)),0)。

对于一般情况：

发现本质的差别是有点状态不能走了，本质上能走的转移就是在 [L+k,R] 处有匹配的结尾，也就是 \text{endpos} 集合中有元素在这个区间里。