cnblogs 怎么又炸了。只能先写在这里了。
为什么又可爱又强的 xxn 去年 9 月就会的科技樱雪喵现在还不会呢 /kel。
感觉 SAM 的教程已经被前人写烂了啊。那就写点个人学习过程中对 SAM 的理解。
参考资料：KesdiaelKen-史上最通俗的后缀自动机详解、OI wiki-后缀自动机 (SAM)。
概述
SAM 是一个能够在线性时间内解决很多字符串问题的算法。
比如对于 \(s=\mathtt{"abb"}\)，构造出的 SAM 形如下图：
看得出来，它是一张有向无环图，其中每条边上标有一个字母表示转移。在图上的任意一条路径，把它经过的边上的字符接起来，都是 \(s\) 的一个子串。相应地，\(s\) 中的任意一个子串都能在 SAM 中找到至少一条对应的路径。
设 SAM 的起点为 \(t_0\)，则字符串 \(s\) 的任意一个后缀都存在唯一一条从 \(t_0\) 出发的路径与之对应。
SAM 就是用来构造满足上面条件，且点数与边数均最小的图的算法。
SAM 的点数（状态数）上界为 \(2n-1\)，边数（转移数）上界为 \(3n-4\)，时空复杂度均为 \(O(n)\)。证明可以看 OI-wiki，因为对做题帮助不大所以这里不赘述。
在构建 SAM 之前，先要了解一些基本的概念和结论。
endpos
假设 \(t\) 为 \(s\) 的一个非空子串，我们定义 \(t\) 在 \(s\) 中的所有结束位置构成的集合为 \(\text{endpos}(t)\)。例如对于 \(s=\mathtt{"abaab"}\)，\(\text{endpos}(\mathtt{"ab"})=\{2,5\}\)。
那么 \(s\) 的所有子串 \(t\)，可以根据它们 \(\text{endpos}\) 的不同，将子串划分为若干个等价类。
为方便后文对 \(\text{link}\) 性质的总结，这里定义 \(\text{endpos}(\mathtt{""})=\{0,1,\dots,|s|-1,|s|\}\)。
而这也就是 SAM 中节点的定义。SAM 中的每个节点恰好对应地表示一个 \(\text{endpos}\) 等价类，所有从 \(t_0\) 到这个点的路径表示的子串，它们的 \(\text{endpos}\) 都相同，并与以其他点为终点的均不同。
因此，SAM 的节点个数即为 \(s\) 所有子串不同的 \(\text{endpos}\) 等价类个数 \(+1\)（起点）。
根据 \(\text{endpos}\) 的定义，它有如下性质：
性质 1：若子串 \(u\) 和 \(w\) 属于同一等价类，且 \(|u|<|w|\)，则 \(u\) 每次出现在 \(s\) 中，都作为子串 \(w\) 的后缀。
反证，若存在 \(u\) 在某个结束位置 \(x\) 出现，且它不是 \(w\) 的后缀，那 \(w\) 没法也在 \(x\) 位置出现，与它们属于同一 \(\text{endpos}\) 等价类矛盾。
性质 2：对于两个非空子串 \(u\) 和 \(w\)（\(|u|<|w|\)），必然满足 \(\text{endpos}(u)\cap\text{endpos}(w)=\varnothing\) 和 \(\text{endpos}(w)\subseteq\text{endpos}(u)\) 其中之一。
- 若 \(u\) 为 \(w\) 的后缀：所有出现 \(w\) 的位置一定会同时存在子串 \(u\)，而出现子串 \(u\) 的位置不是一定有 \(w\)。故此时 \(\text{endpos}(w)\subseteq\text{endpos}(u)\) 成立。
- \(u\) 不是 \(w\) 的后缀：依旧反证，如果有一个位置同时是它们两个的 \(\text{endpos}\)，\(u\) 一定得是 \(w\) 的后缀，与条件矛盾。此时 \(\text{endpos}(u)\cap\text{endpos}(w)=\varnothing\) 成立。
性质 3：将一个 \(\text{endpos}\) 等价类所包含的所有互不相同子串按长度升序排序，任意两串长度不相等，每个串都是下一个串的后缀，且长度差为 \(1\)。
- 若存在两个串长度相等，\(\text{endpos}\) 相同，那这两个串一定相同，与子串互不相同矛盾。
- 设存在两个串 \(u\) 和 \(w\) 的 \(\text{endpos}\) 相同，且 \(|w|-|u|>1\)。设 \(v\) 为 \(w\) 的一个后缀，且 \(|u|<|v|<|w|\)。那么由性质 1 知，\(u\) 是 \(v\) 的后缀。那么由性质 2，得 \(\text{endpos}(w)\subseteq\text{endpos}(v)\subseteq\text{endpos}(u)\)。又因为 \(\text{endpos}(u)=\text{endpos}(w)\)，则 \(\text{endpos}(w)=\text{endpos}(v)=\text{endpos}(u)\)。证得 \(v\) 也必定属于该等价类。
link
对于 SAM 上除 \(t_0\) 外的点 \(v\)，设它包含的子串中最长的一个是 \(w\)。定义这样的 \(w\) 的长度为 \(\text{len}(v)\)。
根据上文的性质 3，我们知道：一段连续的，长度在 \([x,|w|]\) 之间的 \(w\) 的后缀属于该等价类。在这里，我们定义点 \(v\) 的后缀链接 \(\text{link}(v)\) 表示 \(w\) 最长且 \(\text{endpos}\) 不等于 \(v\) 的后缀所属的等价类节点。
对于 \(\text{link}(v)\)，有如下性质：
性质 4：把所有 \(v\) 和 \(\text{link}(v)\) 连边，则后缀链接构成一棵以 \(t_0\) 为根的树。
- 根据定义，\(\text{link}(v)\) 包含的子串均为 \(v\) 子串的后缀。那么跳后缀链接过程中，子串长度单调递减，最后必然能跳到空串，即 \(t_0\)。
性质 5：对任意节点 \(v\)，都有 \(\text{endpos}(v)\subsetneqq\text{endpos}(\text{link}(v))\)。
- 由性质 2 和后缀链接的定义，\(\text{link}(v)\) 包含的子串是 \(v\) 包含的后缀，故 \(\text{endpos}(v)\subseteq\text{endpos}(\text{link}(v))\)；
- 它们一定不相等，因为如果相等应该合并成一个点。
同时，我们得到关于 \(\text{minlen}(v)\) 的表达式：\(\text{minlen}(v)=\text{len}(\text{link}(v))+1\)。
正片开始
SAM 的构造
这是一个在线算法，也就是说我们逐一加入字符，并对应地构造出当前字符串的 SAM。现假设已经构造完了串 \(s\)，要在 \(s\) 后面添加一个字符 \(c\)。
这里先粘个板子，再逐一解释每句代码的含义。
void add(int c)
{
int p=lst,np=lst=++tot;
d[np].len=d[p].len+1;
for(;p&&!d[p].ch[c];p=d[p].fa) d[p].ch[c]=np;
if(!p) {d[np].fa=1;return;}
int q=d[p].ch[c];
if(d[q].len==d[p].len+1) d[np].fa=q;
else
{
int nq=++tot; d[nq]=d[q];
d[nq].len=d[p].len+1,d[q].fa=d[np].fa=nq;
for(;p&&d[p].ch[c]==q;p=d[p].fa) d[p].ch[c]=nq;
}
}
背下来背下来。 跟 SA 不一样，亲测 SAM 在不理解的情况下背下来完全没法做题。
int p=lst,np=lst=++tot;
d[np].len=d[p].len+1;
在已有的字符串后面接了一个 \(c\)，考虑多了哪些子串：原来 \(s\) 的每个后缀（包含空串）后面接一个 \(c\)。
设 \(lst\) 为原来表示整个 \(s\) 串的点，即 \(\text{endpos}=|s|\) 的点；那么 \(s+c\) 这个字符串用现在的 SAM 肯定表示不出来，我们要建一个新点 \(np\)，并连一条 \(lst\to np\) 的边来表示新串。
那么这个新点包含的最长子串长度显然为 \(|s|+1\)，即 \(\text{len}(lst)+1\)。
for(;p&&!d[p].ch[c];p=d[p].fa) d[p].ch[c]=np;
if(!p) {d[np].fa=1;return;}
我们现在的 SAM 表示出了 \(s+c\) 这一整个子串，接下来我们要让 \(s\) 的每个后缀后面都接上 \(c\) 这个转移。
对于第一个循环，p=d[p].fa 就是枚举 \(s\) 的所有后缀，并让它向 \(np\) 连边。如果循环过程中没有发现一个 \(p\) 连过 \(c\) 这条边，代表新串的所有后缀都没有在原串中出现过，它们的 \(\text{endpos}\) 都是 \(|s|+1\)，那么根据 \(\text{link}\) 的定义，第一个不属于该等价类的后缀就是空串，即 \(\text{link}(np)=t_0\)。
否则如果跳的过程中发现有一个 \(p\) 连过 \(c\) 这条边了，那么 \(p\) 的后缀链接自然也都连过 \(c\) 边，无需继续循环；则接下来的后缀都是以前在 \(s\) 里就出现过的子串，要把这种情况拿出来继续讨论。
int q=d[p].ch[c];
if(d[q].len==d[p].len+1) d[np].fa=q;
这里需要讨论 \(\text{len}(p)\) 和 \(\text{len}(q)\) 的关系。
考虑 \(\text{len}(q)=\text{len}(p)+1\) 的实际含义。感觉这里很神秘啊。
对于所有连向点 \(q\) 的点 \(p\)，里面显然只有一个点满足 \(\text{len}(q)=\text{len}(p)+1\)。那如果这条边正好是 \(c\)，就代表 \(\text{longest}(q)=\text{longest}(p)+c\)。
根据 \(\text{endpos}\) 的性质 3，这就保证了 \(q\) 包含的所有子串都是新字符串的一个后缀。它们的 \(\text{endpos}\) 集合都增加了一个 \(|s|+1\)，依旧属于同一个等价类，不用改动。
而 \(\text{link}(np)\) 自然也就是 \(q\)。
else
{
int nq=++tot; d[nq]=d[q];
d[nq].len=d[p].len+1,d[q].fa=d[np].fa=nq;
for(;p&&d[p].ch[c]==q;p=d[p].fa) d[p].ch[c]=nq;
}
到了最抽象的部分！
\(\text{len}(q)>\text{len}(p)+1\) 的话，\(\text{longest}(p)+c\) 是 \(\text{longest}(q)\) 的一个后缀。也就是说，\(q\) 包含的所有子串中，只有长度不大于 \(\text{len}(p)+1\) 的这部分后缀出现次数又增加了 \(1\)。我们被迫把原来全部属于 \(q\) 的子串分进两个不同的等价类里面。
新建一个节点 \(nq\)，表示从 \(p\) 转移过来，出现次数增加了 \(1\) 的这部分子串。虽然这部分被单独分出来了，但它的后续转移跟新加的 \(c\) 并没有关系，可以从 \(q\) 直接复制过来。
考虑被分出来的子串是 \(q\) 中比较短的那一部分后缀，而且它们也是新串的后缀。故有 \(\text{link}(q)=\text{link}(np)=nq\)。
循环的作用是把原来连在 \(q\) 的边都改到 \(nq\) 上去。
至此，我们成功地构建了一个 SAM 。
应用
貌似 SAM 能做的事 SA 也差不多都能，所以合一起口胡一下做法。
判断字符串是否出现
-
SAM
把文本串的 SAM 建出来。根据任意一个子串都能被 SAM 上一条以 \(t_0\) 为起点的路径表示的性质，从起点开始顺着模式串字符的转移边跑，能跑完整个模式串就是出现了。 -
SA
对文本串 \(s\) 跑 SA，模式串如果出现就一定是 \(s\) 的一个后缀的前缀，在排序后 \(s\) 的所有后缀中逐位二分即可确定它所在的位置。
不同子串个数
-
SAM
两种做法。
从 SAM 上转移边的角度考虑，不同的子串个数即为从 \(t_0\) 出发的不同路径数。设从点 \(u\) 出发的路径数为 \(f_u\)，则有转移：\(f_u=1+\sum\limits_{u\to v} f_v\)，答案为 \(f_{t_0}\)。
从后缀树的角度考虑，我们知道 \(\text{minlen}(v)=\text{len}(\text{link}(v))+1\)，则属于点 \(v\) 的 \(\text{endpos}\) 等价类的子串个数为 \(\text{len}(v)-\text{len}(\text{link}(v))\)。总个数为每个节点的答案之和。 -
SA
不同子串个数本质上求的是 \(\frac{n(n+1)}{2}-\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n \min\{\text{height}_i,\text{height}_{i+1},\dots,\text{height}_{j}\}\)。使用单调栈处理出 \(i\) 左右首个比自己小的数的位置，即可统计贡献。似乎也可以从大到小填数，用并查集维护两边的 \(size\)？
字典序第 \(k\) 大子串
-
SAM
预处理从每个点出发的路径数，那么可以快速地判断是否要走当前转移边。按字典序从小到大枚举转移边，直到确定第 \(k\) 个子串包含在里面即可。
如果本质不同的算成多个，就在处理 \(f_u\) 时把同一个点包含的子串个数计入贡献。 -
SA
排序后从前往后枚举每个后缀，它对答案的贡献就是总长度去掉 \(\text{height}\)。
对于本质不同算多个好像挺麻烦的，具体可以看 这篇博客。
子串出现次数
-
SAM
找到该子串在 SAM 上对应的点，从这个点出发能走到的终止状态数就是子串出现的次数。这个东西可以在后缀树上 DP，注意求的不是从这个点出发的路径数。 -
SA
与判断字符串是否出现方法一致，使用二分找到以该子串作为前缀的 \(sa\) 区间。
最长公共子串
- SAM
要求 \(S\) 和 \(T\) 的最长公共子串，我们先对 \(S\) 构造 SAM，然后再对 \(T\) 在 SAM 上进行匹配。具体地，对于 \(T\) 的每个前缀，我们在 \(S\) 上找最长的（\(T\) 的这个前缀）的后缀。
听起来很绕。换句话来讲：逐一往 \(T\) 后面添加字符，维护当前 \(T\) 的后缀在 \(S\) 上最多匹配到哪里。我们维护两个变量 \(now\) 和 \(len\)，表示当前 SAM 上匹配到的节点 & 匹配的字符串长度。
考虑在 \(T\) 末尾新加入字符 \(c\) 对答案的影响。若 \(now\) 有字符 \(c\) 的转移边，则沿边转移，\(len\leftarrow len+1\)；否则不断跳 \(\text{link}(now)\) 直到存在该转移边，并令 \(len=\text{len}(now)\)。在这个过程中记录 \(len\) 的最大值即可。
关于这里为什么令 \(len=\text{len}(now)\) 是对的：如果实际匹配的长度大于 \(\text{len}(now)\)，那在上一次跳 \(\text{link}\) 的时候就应该能转移。如果实际匹配的长度小于 \(\text{len}(now)\)，那加入 \(c\) 之前，原来的 \(now\) 和 \(s\) 根本对不上，与上一轮已经匹配正确的前提矛盾。 - SA
相比之下 SA 处理这个就很简单，把两个字符串接在一起，最长公共子串所属的后缀，排完序肯定挨在一起，所以满足 \(sa_i\) 和 \(sa_{i-1}\) 不属于同一个串的 \(\text{height}\) 的最大值就是答案。
多个串的最长公共子串
- SAM
看到两种主流做法。
一种是 OI-wiki 说的把所有串并在一起跑 SAM，然后根据特殊字符判断。但是奈何这只菜喵没看懂，也没找到其他相同做法的资料，这里挂个 Link，有神仙看懂了的话浇浇樱雪喵 /kel
另外一种是对最短的子串建 SAM，并依次考虑其他串，在 SAM 上记录每个点的最大匹配长度的最小值。然后答案是（这些最小值）的最大值。（禁止套娃。 - SA
把所有串并在一起跑 SA。二分最长公共子串的长度 \(k\)，对于每个 \(\text{height(i)}\ge k\) 的连续段判断是不是在每个串中都出现过即可。
一些闲话
个人感受就是想得明白的话 SAM 比 SA 好写一点，但是属实过于费脑子。时间复杂度虽然不一样，但 SAM 的 \(26n\) 空间常数摆在那里估计也没人对着 SA 的 \(\log\) 卡（？）会哪个写哪个就好了。
于是学个 SAM 板子学了一天，并且可以预见到未来的几天内我又会把它忘得一干二净。什么时候能变得有效率呢！
那就完结撒花吧 >w<