就本着认真负责的态度来一点SAM咸化吧。
其实是杜教筛推不动了来划水了。
刚开始学SAM的时候，翻遍了各种博客和题解，但是都没有看太懂。
直到后来去借助某可视化网站，一点一点去看，才懂了一点。
于是，想着来搞一个不一定详细但是适合入门的SAM咸化。
放上SAM可视化
注意：本蒟蒻对SAM的理解非常浅，写错了那就错了吧。
本文章并不会证明SAM的各种性质，所以请巨佬们忽略本文。
- 什么是SAM
是后缀自动机。
此部分完结。
（下面的内容含有不严谨成分，后面再说明）
可以类比一下AC自动机，就是一张基于trie树的图。
根据名字可知，这个自动机只接受相应字符串的后缀。
然而事实上不是这样。我也不知道为啥这寄吧叫后缀自动机。
这个自动机的性质是，它可以接受相应字符串的任意子串。
换句话说，从根节点开始的任意一条路径，都是字符串的一个子串。
我们记字符串长度为 \(n\) 。
这个寄吧的一个优秀性质是，节点个数不会超过 \(2n - 1\) ，转移边的个数不会超过 \(3n - 4\) 。这也保证了其复杂度。
给一些前置约定。
SAM的每个节点包含三样东西：
\(len\) 表示最长长度。后面详细说。
\(link\) 类比一下AC自动机里面的 \(fail\)。
\(edge[26]\) trie树上的边。
如果没有特殊说明，以后说SAM上的边就指 \(edge\) ，与 \(link\) 无关。
前文所说的“路径”也不包含 \(link\) 。
2.构建
先不说理解性质的问题。
要是SAM建都建不出来理解了也没啥用。
接下来介绍一下常规的 \(O(n)\) 构建法。
我也确实没见过其他复杂度的构建法。
首先说明一个概念，\(endpos\) 。
假设我们有一个字符串 \(S\) ，记 \(S[i,j]\) 表示 \(S[i] \to S[j]\) 这一个子串。
（下标从 \(1\) 开始）
那么 \(endpos(S[i,j])\) 表示一个集合，这个子串在 \(S\) 中的所有出现位置。
我们以结尾位置的下标来表示出现位置。
如果上面那一堆没看懂的话，来看个例子吧。
\(S = "abcbc"\)
则 \(S[2,3] = "bc"\)
于是我们有，\(endpos(S[2,3]) = endpos("bc") = \{3, 5\}\)
要是再没懂建议好好再看看。
然后我们说完了 \(endpos\) 的定义，发现这东西没啥用。
那就扔了吧我们去引入别的概念。
为了方便使用，我们再引入几个小结论：
- 对于 \(S[i,j]\) 以及其后缀 \(S[k,j]\ (i < k \le j)\) ，我们有
如果要感性证明一下的话，我们可以发现 \(S[i,j]\) 出现过的位置 \(S[k,j]\) 都出现了，而 \(S[k,j]\) 出现过的位置 \(S[i,j]\) 不一定出现，所以是包含关系。
- 两个不同子串的 \(endpos\) 要么是包含关系要么就不相交。
感性证明的话考虑反证。如果子串 \(S_1\) 和 \(S_2\) 的 \(endpos\) 集合相交，则存在一些位置 \(S_1\) 和 \(S_2\) 的结尾重合，所以 \(S_1\) 和 \(S_2\) 其中一个为另一个的后缀。
又根据结论 \(1\) ，则两个子串的 \(endpos\) 集合必定为包含关系。所以不会出现相交而不包含的情况。
- 一个 \(endpos\) 集合可以表示一些后缀相同、长度连续的子串。
严谨的讲，一个 \(endpos\) 集合可以表示的子串为 \(S[a,b]\) ，其中 \(b\) 为定值，\(a\) 属于某个范围 \([l,r]\) 。
感性证明就免了吧。直接根据结论 \(1\) 和结论 \(2\) 就可以推出来。
总是要自行思考的，我就不多嘴了。
就先有这三个结论就够了。
然后我们来换一个角度理解SAM：
首先，每个节点表示一个 \(endpos\) 集合，代表一堆子串，这堆子串有着相同的 \(endpos\) 。
当然，我们并不维护其 \(endpos\) 集合本身。
关于 \(len\) ：
一个节点表示的子串里面，最长的长度我们记为 \(len\) 。可以发现其它的子串都是这个最长子串的后缀（因为结论 \(3\) ）。
关于 \(link\) ：
之前我们说过 \(link\) 的意义类似于 \(fail\) 。实际上 \(link\) 表示的是 \(endpos\) 比这个节点大并且包含这个节点的 \(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(link(v)) < len(v)\)
\(len(v) < len(v.edge[c])\)
有了这两个性质，我们就可以用桶排序来代替拓扑排序了。
只需要对 \(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\) 跳，同时置 \(p.edge[S[i]] = ka\) ，直到 \(p.edge[S[i]] \neq q\) 或者 \(p = 0\) 为止。
-
最后，置 \(link(now) = link(q) = ka\) ，结束构建。
烷氮，到这里事情的发展已经完全超出预期了。
这里的操作比较密集并且完全看不懂在干什么。
好了后面不会了本文结束。
后面提供一份代码然后我就跑路。
注意，后面建议慢点读，开始出现数字了
首先我们回忆一下前面都干了点啥。
让 \(p\) 从 \(last\) 一路跑到 \(p\) ，同时路上置 \(p.edge[S[i]] = now\) 。
我们记跳到 \(p\) 之前的那个点是 \(x\) ，那么从 \(now\) 到 \(x\) ，我们把这一堆子串后面加上 \(S[i]\) 形成的子串都存在了 \(now\) 里面。
也就是说现在 \(now\) 节点表示的长度为 \([len(last) + 1, len(p) + 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真的是太难了。。。