SAM 略解

g1ove · 2024-03-06 18:29:22 · 个人记录

前言

只要你愿意啃，没有算法是学不来的 ——教练

说实话，学完 SA 后有时间都会去看 SAM ，但就是怀着信息去，带着一脑子问号回来

根据教练の哲理，一定要把 SAM 啃下来

引入

后缀自动机能解决很多问题。

举个例子

• 在一个字符串中搜索另一个字符串所有出现位置
• 得到有多少本质不同的字串

当然，这些 SA 也能轻易完成 但是 SAM 能做到很多 SA 做不到的 它最大的优势是在线的 而且它有十分优秀的时间复杂度 O(n)

SAM 的定义

• SAM 是一张有向无环图 只有一个原点 t_0 称为初始状态 其它所有点都可以通过 t_0 到达
• 每条边都是一个转移 每个节点都是一个状态
• 每个状态的转移都是不同的
• 存在多个终止状态，满足从原点 t_0 出发，到达终止状态立得到的字符串的必是原字符串的后缀 并且满足任何 S 的后缀都可以由一条路径表示
• 满足上述所有条件前提下，SAM 满足节点数最少

SAM 的基本性质

SAM 保证：

• 字符串中的任意一个字串都可以由一条路径表示
• SAM 任意一个节点表示的字符串都是原串 S 的字串

一些例子

可以前往 OI-wiki 查看

一些重要的概念

endpos

定义：我们记 \text{endpos(p)} 表示字符串 p 在原串 s 中所有出现结束位置的集合。 举个栗子，对于 \text{s=ababa} 则 \text{endpos(ab)}=(2,4) ，\text{endpos(a)}=(1,3,5)

对于两个字串 a , b ,若满足 \text{endpos(a)}=\text{endpos(b)} 我们认为 a,b 是一个等价类。 因此，S 里面所有的字串可以分成若干个等价类。 而我们 SAM 中的节点，就是所有等价类带边的点

一些定理/引理

这个感性证明是最好的，自行理解就行

也是推荐感性理解，长度 x 以下的是当前集合的超集，y 以上的是当前集合的子集 这个区间内一定都是连续的数字，因为字串是连续的 不理解可以看看例子

• 1.3

  对于任意两个子串 a,b\space |a|\le |b| 如果 a 为 b 的后缀，那么它们满足 1.1 否则满足 endpos(a)\cup endpos(b)=\varnothing

根据 1.1 可以推证

后缀链接 link

先看张图

红色的边就是后缀链接

其实用最直白的话来讲 后缀链接就是当前等价类最短后缀的下一个后缀 就是当前等价类的超集 比如说 \text{abcbc} 它的最短后缀是 \text{abc} 那么它连接到的就是 \text{bc} 因为 \text{endpos(bc)}=\{2,4\}

还是很好理解的 手画一下其它节点都满足这个性质

考虑对于任意节点往后缀链接移动，能满足当前等价类的长度不断变短，最终总能到达 t_0 根据 1.3 可以证明不存在环 所有点联通不存在环的无向图就是树

对于这棵树 我们称为 \text{parent tree}

• 2.2$ 对于任意状态，记它的长度区间为 $[l,r]$ 那么对于任意节点 $x$ 满足 $l_x$ = $r_{fa_x}+1
• 2.3$ 对于任意状态 $v_0$ 向着 $\text{link}$ 遍历到 $t_0$ 经过所有状态长度区间的交集为 $\{0\to r[v_0]\}

即从任意状态往 t_0 走，可以完成遍历完它的所有后缀

我们 SAM 的状态点与 parent tree 的状态是完全相同的

对于一整个字符串 s 它只会在 parent tree 中分裂 |s| 次 所以可以保证节点在最坏条件下是 2n-1 的

知道这些后，我们可以开始构造 SAM 了

SAM 的构造

SAM 是一个不停往后加字符的在线算法

SAM 是和 parent tree 同时构造的

构造流程 (PS:一定要在纸上边画图边写)： 现在我们要加入字符 c

• 2$ 创建一个新节点 $\text{cur}$ 表示当前节点 令 $\text{len(cur)=len(last)+1}

  这一句话的意思是当前等价类的最长长度是上一个的 +1 非常显而易见的性质

• 我们知道 一直跳 $\text{link}$ 可以遍历完所有后缀 这个过程相当于向每个后缀加一条出边
• 4$ 如果跳到了原点 $p$ 令 $\text{link(cur)}=0$ 转 $8

  为什么呀？为什么？ 一个点跳到原点都没有 c 的出边 意味着遍历了当前所有后缀的前缀都没有 c 所以 c 是第一个出现的字符 直接把 link 设为原点即可

• 为什么呀？为什么？ 首先 我们先说明 ${len(q)}\ge {len(p)+1}$ 因为 $q$ 是 $p$ 转移来的 这是非常显然的 然后 相等是一个特殊情况 我们考虑为什么要给等价类连边 不就是在当前字符串满足后缀长度最小时 前面有相同部分出现吗 那么 把后缀同时去掉一个 $c$ 求得的也是相同的 也就是说 $\text{len(p)}+1$ 得到的就是 $\text{link(cur)}$ 的最长开始重复部分 也就是下一个等价类 $q$ 刚好满足 直接连接即可 转 $8
• 因为我们通过 $6$ 的分析 是可以直接 $link$ 的 但是不等却不行 为什么呢 因为这样跳上去的节点存在部分不是 $cur$ 的后缀 这个时候我们直接把这个节点分裂成两个 $q$ 和 $copy$ 令 $\text{len(copy)=len(p)+1}

  然后把 q 的 \text{link} 设为 copy 再把 cur 的 \text{link} 设为 copy 即可 这样点之间的我们就处理完毕了 考虑边之间的关系 注意开始 copy 和 q 的出边也是相同的 思考一下这是对的 接着就是入边 我们发现入边情况就多了 要分成连向 copy 和 q 两种情况分类讨论 当然一开始还是所有边都连向 q 现在考虑拆边 我们考虑为什么有边要连向 copy 因为它比 q 长度小 也就是说 只要从 p 继续往上跳 跳到有出边 c 而且长度再 copy 区间内 直接不连 q 连 copy 即可 否则如果连的不是 q ，而是 q 的祖先 说明这些是新的等价类 跳出循环即可 根据往后后缀长度或越来越短 我们保证肯定每个后缀都会有 c 的出边 所以一直操作即可 转 8

• 8$ 令 $last=cur$ 转 $1

这样就完成了

时间复杂度

是线性的 我们认为是 O(n\log \sum) 的 \sum 是字符集的大小 根据代码 我们知道 SAM 只有 2n-1 个节点 3n-4 条边

构建结束标记

我们只需要在当前最后状态往上跳 link 就能遍历完最大后缀 然后结束标记都是在最后在最后结束的 直接打标记即可