SAM
Tangninghaha · · 算法·理论
看了一篇博文，写得很好，让我这个大人机弄明白了 SAM 是什么。
参见
SAM 的定义
SAM，后缀自动机。储存了一个字符串的后缀信息。
-
SAM 是一张 DAG，节点称为 状态，边称为 转移。
-
DAG 有一个 初始状态（节点）
P ，其余所有状态（节点）可以通过一些转移（边）到达。 -
每一个转移（边）标记 了字符集中的一个字母（边权）。从一个状态（节点）出发的所有边（转移）互不相同。
-
将从初始状态（节点）到一个 终止状态（节点）经过的所有转移（边）上的标记连接起来，就能得到原串的一个后缀。反之，原串的 任意 一个后缀可以被表示为从初始状态（节点）到某一个终止状态（节点）的路径。
-
在满足上述条件的 DAG 中，SAM 所使用的节点数最少，为
O(n) 级别，其中n 是原串长度。（最小性）
正是因为最小性，才能满足我们日益增长的效率需要。所以我们要研究这个 SAM，来使得人机能通过 图灵测试 字符串毒瘤题。
注意到原串的后缀的前缀对应了原串的子串，从起始节点走到终止节点，表示一个后缀，而这条路径上除起点以外任意一个节点都表示原串的一个非空子串。不难发现，由于 SAM 能表示任意后缀，任意子串也能被 SAM 表示，这样
后缀链接
后缀链接通过连接 SAM 中的节点，形成了一棵树的结构。
结束位置与等价类
约定字符串下标从
假设字符串 endpos(s) 表示 endpos(s) 必定非空。
S="abab"
s = "a" "b","ab" "aba","ba" "abab","bab"
endpos(s) = {1,3} {2,4} {3} {4}上面是一个例子。
显然，两个子串的
注意
SAM 上的一个节点对应一个等价类。
引理
画画图感受一下，这些都是对的。
-
两个子串
\text{endpos} 集合相同，等价于，一个子串是另一个子串的后缀 并且 较短串只作为较长串的后缀出现。 -
若
s_1 是s_2 的后缀，且s_1 较长。则较短串\text{endpos} 集合包含（不一定真包含）较长串的\text{endpos} 。否则，两集合交集为空。是后缀时，较长串出现时，较短串必然出现，较短串出现时较长串不一定出现。
不是后缀时，假设存在两集合交集非空，取交集中任一位置，则两个串均以这个位置为结尾出现过，则较短串必定是较长串的后缀，与假设矛盾。
-
一个
\text{endpos} 集合不包括两个等长但是本质不同的子串。如果等长，出现位置又完全一样，难道有可能本质不同吗？
-
一个等价类中，任意两个串，较短者为较长者的后缀。
由引理 1 可以得到。有了这个引理，一个等价类中，其余串均是最长串的后缀。
-
若一个等价类中最短字符串为
l ，最长字符串为r ，则[l,r] 之间的长度均在该等价类中出现过。可以反证，假如有一个长度没有出现过，显然是不可能的。
后缀链接的定义
上面提到，SAM 中每一个节点对应一个等价类，设
记串
即
由定义得，设一个等价类
这启示我们，如果知道
由引理 2，
所有后缀链接构成了一棵树的形态。对于每一个节点（等价类），其后缀链接节点中最长串长度，小于此节点最短串长度。则沿着后缀链接遍历，每一个等价类中的串长度只会减少，不会成环。此外，除初始节点
小结与记号约定
-
原串
S 每一个子串根据\text{endpos} 划分为多个等价类，每一个等价类对应 SAM 上的一个节点。 -
对于每一个节点（等价类）
v ，定义\text{long}(v) 表示其最长的串，\text{len}(v) 表示其长度；\text{short}(v) 为最短的串，其长度可以表示为\text{len}(\text{link}(v))+1 。 -
从任意点
v_0 出发总能到达P ，经过的节点v_i 的等价类表示的串，均为\text{long}(v_0) 的后缀，且长度[1,\text{len}(v_0)] 恰好各出现一次。 -
所有后缀链接形成一棵以
P 为根的根向树。 -
后缀链接也可以表示
\text{endpos} 的包含关系：父亲节点包含儿子节点。 -
注意，后缀链接和 SAM 实际上是共用点，而各自有边的两张图。SAM 是一个 DAG，描述了字符串的转移，后缀链接树是树，描述了等价类的包含关系。
SAM 的线性构建算法
先从算法流程出发，再分析原理。
算法流程
此算法是一个 在线算法，每一次在已经构建好的串
-
记
last 为上一次构建结束后停在的节点处，这个节点表示S 所属的等价类。在插入结束部分对last 进行更新。 -
现在插入一个字符
c 。新建一个节点cur ，将\text{len}(cur) 设置为\text{len}(last)+1 。 -
从
last 开始遍历last 的后缀链接，如果当前节点v 没有c 的转移，则加入一条v\rightarrow cur 的边，标记（边权）为c 。 -
如果遍历到了起始节点
P ，则到第 8 步。 -
如果遍历到节点
v 时，发现v 有到c 的转移，记当前节点为p ，其转移到q 。 -
如果
\text{len}(p)+1=\text{len}(q) ，将\text{link}(cur) 设置为q ，转到第 8 步。 -
否则，创建一个
copy 节点，复制q 的所有信息到copy 中，包括link 和所有出边。将\text{len}(copy) 设为\text{len(p)}+1 。然后，设
\text{link}(q)=copy ，\text{link}(cur)=copy 。从
p 遍历后缀链接，设当前遍历到了点v ，若v 有边权为c 的出边，且连向q ，则将这条边连向copy 。如果
v 没有边权为c 的出边，或是出边不连向q ，则停止遍历，转到第 8 步。 -
把
last 赋值为cur ，转到第 1 步。
算法原理
-
-
现在插入字符
c 之后，必然产生一些新的子串，这些子串是S+c 的一个后缀，其\text{endpos} 集合必然包含新的末尾位置。所以一定会产生新的等价类，新建一个cur 节点记录该等价类的信息。此等价类的最长串显然是S+c ，其长度为\text{len}(last)+1 。 -
从
last 遍历后缀链接，遍历到的节点均为S 的后缀，且一直没有遇到有c 转移的。考虑某一个后缀s 没有到c 的转移，那么s+c 必然属于S+c 这个等价类集合。 -
如果走到了初始节点
P 也没有遇到转移c ，说明c 在原串中没有出现过，此时直接结束即可。 -
如果遇到一个节点有到
c 的转移，就需要进行一些维护。 -
由于
\text{endpos}(p) 的真包含\text{endpos}(last) ，必定存在一些位置在\text{endpos}(p) 而不在\text{endpos}(last) 中。且\text{long}(p) 是满足这个条件的最长的串。由于
p 有边权为c 的转移，故\text{long}(p)+c 是原本存在的，且这个串是满足，最长的，与S+c 的\text{endpos} 集合不同的串。如果
\text{len}(p)+1=\text{len}(q) ，则\text{long}(p)+c 是q 等价类中最长串，直接将cur 的后缀链接连到q 即可。 -
如果不满足上述条件，说明
\text{long}(p)+c 不是\text{len}(q) 中最长的串，那么需要将q 分裂为两个部分。一部分的长度在
(\text{len}(p)+1,\text{len}(q)] 之间，这部分并不会作为S+c 的后缀出现，故其\text{endpos} 集合与新的等价类不同。所以建立一个copy 节点，将q 节点的信息复制到copy 节点上（包括转移等），再将copy 节点的\text{len} 设为\text{len}(p)+1 。长度在(\text{len}(p)+1,\text{len}(q)] 之间的一部分仍然使用q 这个节点。修改后缀链接：
-
-
上一段提到，前一部分的
\text{endpos} 集合应当是这一部分的真子集，根据定义，将\text{link}(q) 修改为copy ，\text{link}(cur) 也修改为copy 。
还有一些东西需要修改：原本一些节点通过边权为
c 的边转移到q ，现在，有一些应当转移到copy ，另一些转移到新的q 。沿着p 继续遍历后缀链接，假设到了点v 。-
若
v 有一条边权c 到达q 的边，由于v 是p 的后缀（后缀链接定义），则v+c 一定在copy 集合内，将这条边重定向到copy 。 -
若
v 有边权为c 但是不连向q ，其一定连向q 在后缀链接树上的一个祖先，此时不能将其重定向。此时v 的祖先连向的必然也是q 的祖先，所以也不能重定向，此时无需继续遍历。 -
-
SAM 的复杂度
假设字符集大小为
-
若每一个节点使用
O(\lvert \Sigma\rvert) 的空间，记录每一个边权的转移，还需要一些辅助的东西，做到O(n\lvert \Sigma\rvert) 的空间复杂度，O(n) 的时间复杂度。 -
如使用
map进行实现，则可以做到O(n) 的空间复杂度和O(n\log \lvert \Sigma\rvert) 的时间复杂度。
当字符集较小（例如 26）时常用第一种做法。
SAM 的应用
统计子串
子串是前缀的后缀，在 SAM 的构造中，我们逐个向 SAM 中插入字符，则每一次新建的
Problem A 【模板】后缀自动机
Link
求一个字符串
::: details Solution
在每一个前缀节点打上一个标记，这个标记的作用是：将其所有祖先的出现次数加 1。这样，只要 DFS 一遍树，求子树内的标记数量，就能知道某一个点的出现次数，也即等价类的出现次数。根据等价类的定义，可以知道，等价类中所有字符串的出现次数是一致的，于是只需要考虑其最长的串，即长度为
:::
Problem B 【SDOI 2016】 生成魔咒
Link
初始有一个空串
::: details Solution
一种方法是：在两个字符串中间插入一个神秘字符，使其不在字符集中（使得跨过两个串的子串不被统计）。如果插入的是第一个串中的字符，在结束的
另一种方法：将一个串插入 SAM，另一个串在 SAM 上游走。具体我没有实现，应该跟 AC 自动机上匹配差不多。
:::
另外 这道题 也挺类似的，但是有点不同，可以做一做。