SAM与咸化

H_Kaguya · 2022-12-29 20:07:19 · 个人记录

就本着认真负责的态度来一点 SAM 咸化吧。
其实是杜教筛推不动了来划水了。

刚开始学 SAM 的时候，翻遍了各种博客和题解，但是都没有看太懂。
直到后来去借助某可视化网站，一点一点去看，才懂了一点。
于是，想着来搞一个不一定详细但是适合入门的 SAM 咸化。
放上SAM可视化

注意：本蒟蒻对 SAM 的理解非常浅，写错了那就错了吧。
本文章并不会证明 SAM 的各种性质，所以请巨佬们忽略本文。

1. 什么是 SAM

是后缀自动机。
此部分完结。

（下面的内容含有不严谨成分，后面再说明）

可以类比一下AC自动机，就是一张基于trie树的图。
根据名字可知，这个自动机只接受相应字符串的后缀。
然而事实上不是这样。我也不知道为啥这东西叫后缀自动机。
这个自动机的性质是，它可以接受相应字符串的任意子串。
换句话说，从根节点开始的任意一条路径，都是字符串的一个子串。

我们记字符串长度为 n 。
SAM 的一个优秀性质是，节点个数不会超过 2n - 1 ，转移边的个数不会超过 3n - 4 。这也保证了其复杂度。

给一些前置约定。
SAM的每个节点包含三样东西：

则 S[2,3] = "bc"
于是我们有，endpos(S[2,3]) = endpos("bc") = \{3, 5\}
要是再没懂建议好好再看看。

然后我们说完了 endpos 的定义，发现这东西没啥用。
那就扔了吧我们去引入别的概念。
为了方便使用，我们再引入几个小结论：

1. 对于 S[i,j] 以及其后缀 S[k,j]\ (i < k \le j) ，我们有

   endpos(S[i,j]) \subseteq endpos(S[k,j])

   如果要感性证明一下的话，我们可以发现 S[i,j] 出现过的位置 S[k,j] 都出现了，而 S[k,j] 出现过的位置 S[i,j] 不一定出现，所以是包含关系。

2. 两个不同子串的 endpos 要么是包含关系要么就不相交。

感性证明的话考虑反证。如果子串 S_1 和 S_2 的 endpos 集合相交，则存在一些位置 S_1 和 S_2 的结尾重合，所以 S_1 和 S_2 其中一个为另一个的后缀。
又根据结论 1 ，则两个子串的 endpos 集合必定为包含关系。所以不会出现相交而不包含的情况。

3. 一个 endpos 集合可以表示一些后缀相同、长度连续的子串。

严谨的讲，一个 endpos 集合可以表示的子串为 S[a,b] ，其中 b 为定值，a 属于某个范围 [l,r] 。
感性证明就免了吧。直接根据结论 1 和结论 2 就可以推出来。
总是要自行思考的，我就不多嘴了。

就先有这三个结论就够了。

然后我们来换一个角度理解 SAM：
首先，每个节点表示一个 endpos 集合，代表一堆子串，这堆子串有着相同的 endpos 。
当然，我们并不维护其 endpos 集合本身。

关于 len ：
一个节点表示的子串里面，最长的长度我们记为 len 。可以发现其它的子串都是这个最长子串的后缀（因为结论 3 ）。

关于 link ：
之前我们说过 link 的意义类似于 fail 。实际上 link 表示的是 endpos 比这个节点大的点。
（在这里，我们就感性的认为一个集合比它的子集大好了。。。）

有点抽象？我们换一种说法。

随手掏出来一个子串 S[a,b] ，假设一堆子串 S[k,b]\ (a \le k < c) 有着相同的 endpos ，则会存在某个节点去表示这些子串，我们记这个节点为 v 。
那么同样的，根据结论 1 ，我们会发现 S[c,b] 的 endpos 集合会包含 S[a,b] 的 endpos ，并且更大。
那么就会有另一个节点去表示 S[c,b] ，我们记这个节点为 d 。
于是我们有，link(v) = d。

因此考虑一下跳 link 的过程（感觉就像跳 fail 一样），其实是表示的子串长度在不断缩短的过程，并且每次跳到的是上一次的后缀。

既然跳 link 长度缩短，那么连出来的 link 就不会出现环。同时根据结论 2 我们发现，连出来的一定是一个树。我们称之为 parent 树。
具体性质后面再说。

关于 edge ：
走一条边其实是相当于在后面添加一个字符。这个其实和AC自动机是一样的。
另外，edge 虽然可以被认为是trie树上的边，但是实际上连出来的不是一个树，而是一个 DAG。

一个额外的性质：

有了这两个性质，我们就可以用桶排序来代替拓扑排序了。
只需要对 len 进行排序就可以得到其拓扑序。
更好的是，len 是 O(n) 级别的。

好了，磨叽了这么半天，终于可以开始着手构建了。
我们提供的构建方法是在线的，可以一个字符一个字符的插入。
在最开始，我们有一个空节点 1 作为根节点。
注意，并不存在节点 0 。
首先，假设你已经完成了 S[1,i - 1] 的构建，我们来看看如何插入字符 S[i] 。

• 记上次构建结束的位置为 last ，则我们申请一个新的节点 now ，并且让 len(now) = len(last) + 1 。

这一步还挺显然的，就是新增加一个节点。

• 接下来搞一个指针 p = last ，然后 p 不断往 link(p) 的位置跳，同时置 p.edge[S[i]] = now ，直到 p = 0 或者 p.edge[S[i]] \neq 0 就停止。

这里，我们有必要仔细考虑一下这奇怪的操作是在干啥。

首先，last 节点表示的子串一定是 S[1,i - 1] 及其部分后缀。
而 last 一直往前跳 link 表示的也一定是 S[1,i - 1] 的后缀。
那么我们置 p.edge[S[i]] = now 就很显然了。从 p 这个状态加一个字符 S[i] 一定可以到达 now 这个状态。

同时，现在会有 p.edge[S[i]] == 0 ，也就是说加上 S[i] 之后的这个子串是没有被表示过的。
既然现在出现了那总是要有一个节点来存吧。
我们发现 now 就挺合适，于是就用 now 来存这些子串的信息吧（心情简单）。

• 如果 p = 0 了，让 link(now) = 1 ，然后结束构建。

这一步就是，我们发现 now 这一个节点独自承担了 S[1,i] 及其所有后缀，那也就没有什么好 link 的了，因为下一个后缀就是空串了。
节点 1 表示的貌似就是空串，所以我们就置 link(now) = 1 好了。

• 如果 p \neq 0 ，我们记 q = p.edge[S[i]] ，然后开始后面的分类讨论。

值得一提的是，这里的 q 其实存储的就是 now 的某些后缀的信息。因此直觉告诉我们，可以置 link(now) = q 。
真的是这样吗。。。

• 若 len(q) = len(p) + 1 ，则置 link(now) = q ，然后结束构建。

好，确实是这样。
看样子 SAM 建起来还是挺好理解的。

• 若 len(q) \neq len(p) + 1 ，则新建一个节点 ka ，ka 直接复制 q 的信息，同时让 len(ka) = len(p) + 1。

• 然后，找一个指针 h = p ，然后再让 h 往 link 跳，同时置 h.edge[S[i]] = ka ，直到 h.edge[S[i]] \neq q 或者 h = 0 为止。

• 最后，置 link(now) = link(q) = ka ，结束构建。

这里的操作比较密集并且完全看不懂在干什么。
好了后面不会了本文结束。
后面提供一份代码然后我就跑路。

注意，后面建议慢点读，开始出现数字了

首先我们回忆一下前面都干了点啥。

从 last 一路跑到 p ，同时路上置 p.edge[S[i]] = now 。
我们记跳到 p 之前的那个点是 x ，那么从 now 到 x ，我们把这一堆子串后面加上 S[i] 形成的子串都存在了 now 里面。
也就是说现在 now 节点表示的长度为 [len(p) + 1, len(last) + 1 + 1]
（注意，len(p) + 1 表示的是 x 点表示的子串的最小长度。）

接下来，发现 p.edge[S[i]] \neq 0 ，也就是说这些子串之前出现过，已经被点 q 表示过一遍了。
那么我们显然不能再把这些点划分到 now 里面了。毕竟一个子串不能被重复表示。

但，现在，我们发现 len(q) > len(p) + 1 了，也就是说 q 这个节点表示的子串长度比我们预期的还要更长一些。
则存在另一种子串，它和 S[1,i] 有着公共后缀。

现在显然不能直接把 link(now) 赋值成 q ，因为 link(now) 应该表示的是长度 \le len(p) + 1 的一堆后缀。
但是现在 q 点除了那些后缀以外又多了一些更长的。

所以可以想到的是，我们应该把 q 点分裂，分裂成长度为 [len(p) + 1 + 1, len(q)] 的部分（也就是多出去的部分）和长度 \le len(p) + 1的部分（也就是我们想要的部分）。

我们记 q 为多出去的部分，让一个新建的节点 ka 去表示我们想要的部分。
发现正好有 link(q) = ka 。
顺便，我们的目的也达成了，可以直接置 link(now) = ka 。

但是这就结束了吗？
并没有。

我们发现，我们本来是指望着找到 now 的 link 才跳到的 p ，然后连向了 q 。
换句话说，从 edge 的角度考虑，p.edge[S[i]] 其实想要表示的子串是那个长度为 len(p) + 1 的，而不是那个长度为 len(q) 的。

现在我们把长度 > len(p) + 1 的部分留在了 q 里面，而真正应该由 p 连向的部分在 ka 里面。
当然，顺着 p 节点一直跳 link ，还会有一堆连续的节点也能通向 q 。它们实际链接的子串都是长度 < len(p) + 1 的。这些子串也都存在 ka 里面而不是 q 里面。

于是乎，我们需要去遍历 p 的 link 串，把所有连向 q 的边都改成 p 。

之前学的时候我还有另一个疑惑，为什么不用 q 来表示我们想要的，把多余的扔到 ka 里面。
这样一来，不就不需要再去遍历 p 的 link 串了吗？

而实际上非常不可以。
可能会存在一些节点 m ，link(m) = q 。这个 link 其实锁定的就是长度为 len(q) 的那个子串。
也就是说，如果我们要让 ka 表示多余的，我们需要把 link 指向 q 的全都改成 ka 。
而这显然很难实现。复杂度也不对。

• 最后，记得置 last = now 。

这个没啥好说的。

以上内容没有看懂的话没关系，建议自己多思考，可以再看一遍。
理解 SAM 构建可能对你做题没有太大的帮助，但是还是建议理解一下。

终于，我们的 SAM 建完啦！
完结撒小花~

这里，附上一份我自己打的板子。
（其实各个 SAM 板子基本都类似，自己打一份能记住就行）

#include <map>
#define sz 100005
using namespace std;
struct site
{
    int len, link;
    map<int, int> net;
};
struct site tree[sz << 1 | 1];
int last = 1, top = 1;
void add(int a)
{
    int now = ++top;
    tree[now].len = tree[last].len + 1;
    for ( ; last && (!tree[last].net[a]); last = tree[last].link)
        tree[last].net[a] = now;
    if (!last)
        tree[now].link = 1;
    else
    {
        int q = tree[last].net[a];
        if (tree[q].len == tree[last].len + 1)
            tree[now].link = q;
        else
        {
            int ka = ++top;
            tree[ka] = tree[q];
            tree[ka].len = tree[last].len + 1;
            for ( ; last && tree[last].net[a] == q; last = tree[last].link)
                tree[last].net[a] = ka;
            tree[now].link = tree[q].link = ka;
        }
    }
    last = now;
}

这里，我存 edge 的时候使用了 map 。这样可以支持字符集比较大的情况。
当字符集大小只有 26 的时候（只有小写字母或大写字母），建议还是直接开长度为 26 的数组效率更高。

先写到这里吧。。。
关于 SAM 及其 parent 树的应用还有一大堆，有时间再写吧。
（内容会比上面的多）
到这里已经写了将近 13K 的 Markdown 了，相比写的够细致了吧。
虽然可能更不好看懂的样子。

希望可以对后几届的学长们有用吧。
因为自己学 SAM 真的是太难了。。。

补充一点东西。

我们有经典结论，反串 SAM 的parent 树等价于正串的后缀树。
所以，对于 SAM 上的某个点，指向这个点的 link 最多有 |S| 个。
并且这个上界是可以卡满的。

所以，对于字符集为 26 的字符串，我们可以考虑在新建 ka 节点的时候把多余的东西扔到 ka 里面，然后暴力修改 link。
总体复杂度 O(n|S|)，当我们认为 |S| 为常数的时候和常规写法复杂度相同。

当然，因为需要多记录一些东西所以时空常数会大一点。

顺便，这种写法还是有一些好处的。
容易发现这样子建出来的 SAM 满足 link(a) < a。
需要在 parent 树上 DP 的时候直接倒着扫即可，不需要排序。