2023-08-27

写写 SAM 这抽象玩意。

SAM（Suffix Automaton），后缀自动机，是用来解决有关字符串子串问题的一种数据结构。

我们知道，一个字符串的所有子串，其实也就是所有前缀的后缀。因此我们就诞生了一个想法：把所有后缀都扔到 trie 树上，这样我们就可以直接沿着字符走，并且能够获得所有子串的信息。

但是这样的空间复杂度是能够达到 $O(n^2)$ 级别的。因此我们需要优化一下这个东西，我们可以发现大部分的转移边和点是重复的。因此我们需要把自动机的状态压缩。

在我们考虑这个问题之前，我们先来看另外一种东西，这个东西就是我们压缩自动机状态的关键。

Parent Tree

为了方便叙述，我们定义整个字符串为 $t$ 。

我们定义 $\mathrm{Endpos}(s)$ 为 $s$ 这个字符串在 $t$ 中出现的位置的结尾。比如，我们设 $t=\texttt{abcaabcc}$ ，那么 $\mathrm{Endpos}(\texttt{abc})=\{3, 7 \}$ 。根据 $\mathrm{Endpos}$ ，我们就可以把所有该字符串的子串划分成一堆等价类。

而关于 $\mathrm{Endpos}$ ，有很多性质，这里不再一一证明，仅罗列在下面：

当 $\mathrm{Endpos}(a)=\mathrm{Endpos}(b), |a|<|b|$ 时，在 $t$ 中每次出现时， $a$ 都作为 $b$ 的后缀出现。
两个字符串 $a, b$ （假设 $|a|<|b|$ ），要么 $\mathrm{Endpos}(a) \cup \mathrm{Endpos}(b) = \varnothing$ ，要么 $\mathrm{Endpos}(b) \subseteq \mathrm{Endpos}(a)$
对于同一 $\mathrm{Endpos}$ 等价类的两个子串，其中长度较短者为长度较长者的后缀，且该等价类中字符串的长度完全覆盖 $[x, y]$ 这段区间且不相交。

我们根据这几条性质，我们可以想到树形结构。具体地说，一个等价类可以看作一个点，而等价类的包含关系则对应着树上的父子关系。这样我们就能建立一棵树，而每个点对应的父亲也就是我们在 SAM 中见到的 $\mathrm{link}$ 。

更具体的定义 $\mathrm{link(u)}$ ，即为大小最小的，且包含 $u$ 这个等价类并且不与 $u$ 这个等价类相等的等价类。（OIwiki 上没看懂，因此就自己照着理解写了写）

这里是 OIwiki 的定义

考虑 SAM 中某个不是 $t_0$ 的状态 $v$ 。我们已经知道，状态 $v$ 对应于具有相同 $\mathrm{endpos}$ 的等价类。我们如果定义 $w$ 为这些字符串中最长的一个，则所有其它的字符串都是 $w$ 的后缀。

我们还知道字符串 $w$ 的前几个后缀（按长度降序考虑）全部包含于这个等价类，且所有其它后缀（至少有一个——空后缀）在其它的等价类中。我们记 $t$ 为最长的这样的后缀，然后将 $v$ 的后缀链接连到 $t$ 上。

换句话说，一个 后缀链接 $\mathrm{link(v)}$ 连接到对应于 $w$ 的最长后缀的另一个 $\mathrm{endpos}$ 等价类的状态。

我们再设一个初始状态 $t_0$ ，它的 $\mathrm{Endpos}=\{-1, 0, \cdots |t|-1 \}$ 。这样我们就把根据 $\mathrm{link}$ 构建出的一个森林转化为了一棵树。

同时，我们定义 $\mathrm{len}(u)$ 为 $u$ 这个等价类中，最长的字符串的长度， $\mathrm{minlen}(u)$ 为最短的字符串长度。根据上面的性质 3，我们可以得到下面的结论：

\mathrm{len}({link}(u))+1=\mathrm{minlen}(u)

同时我们也可以得到一个等价类中包含的字符串的个数为 $\mathrm{len}(u)-\mathrm{minlen}(u)$ 。

根据我们上面说的这些，我们构建出来的一棵树就叫做 Parent Tree。

下图是根据字符串 $\texttt{abcbc}$ 构建出的 Parent Tree：

图片来源：OIWIKI

我们可以证明，Parent Tree 中点的个数的数量级为 $O(n)$ 。而对于 SAM，我们就可以利用 Parent Tree 来作为我们 SAM 的节点。

SAM

上面我们介绍了 Parent Tree，我们这里就要利用 Parent Tree 来构建 SAM。

SAM 的构建是在线算法，也就是说，我们可以每加入一个字符然后就进行扩展自动机。

这里先把构建的全过程放在这里：

首先，SAM 初始状态为只有一个节点 $0$ ，表示空节点（也就是 $t_0$ ），为了方便，我们设 $\mathrm{len}(0)=0, \mathrm{link}(0)=-1$ 。

设 $last$ 为添加字符 $c$ 前对应的状态（初始为 $0$ ，最后一步更新 $last$ ）
创建新状态 $cur$ ，令 $\mathrm{len}(cur)=\mathrm{len}(last)+1$ 。
接下来遍历 $last$ 的后缀链接，如果所到的节点没有 $c$ 的转移，那么我们就加入 $c$ 的转移。
如果到达了虚拟状态 $-1$ ，我们就令 $\mathrm{link}(cur)=0$ 并直接跳转到最后。
否则设第一个有 $c$ 的转移的点为 $p$ ， $p$ 通过 $c$ 转移到的点为 $q$ 。
如果 $\mathrm{len}(q)=\mathrm{len}(p)+1$ ，那么我们直接令 $\mathrm{link}(cur)=q$ 并跳转到最后。
否则则进入最麻烦的情况：
- 我们对 $q$ 创建一个副本 $copy$ ，把 $q$ 的后缀链接和转移全部复制给 $copy$ ，同时令 $\mathrm{len}(copy)=\mathrm{len}(p)+1$ 。
- 然后我们把 $\mathrm{link}(q)$ 和 $\mathrm{link}(cur)$ 赋值为 $copy$ 。
- 最后我们再从 $p$ 开始遍历后缀链接，如果遇到向 $q$ 的转移，我们就把它重定向到 $copy$ ，直到转移到的点不为 $q$ 。
最后，令 $last$ 为 $cur$ 。

算法的正确性证明我不会/kk，所以我再把 OIWIKI 的讲解赫到这里/kel。

正确性证明

若一个转移 $(p,q)$ 满足 $\operatorname{len}(p)+1=\operatorname{len}(q)$ ，则我们称这个转移是 连续的。否则，即当 $\operatorname{len}(p)+1<\operatorname{len}(q)$ 时，这个转移被称为 不连续的。从算法描述中可以看出，连续的、不连续的转移是算法的不同情况。连续的转移是固定的，我们不会再改变了。与此相反，当向字符串中插入一个新的字符时，不连续的转移可能会改变（转移边的端点可能会改变）。
为了避免引起歧义，我们记向 SAM 中插入当前字符 $c$ 之前的字符串为 $s$ 。
算法从创建一个新状态 $\textit{cur}$ 开始，对应于整个字符串 $s+c$ 。我们创建一个新的节点的原因很清楚。与此同时我们也创建了一个新的字符和一个新的等价类。
在创建一个新的状态之后，我们会从对应整个字符串 $s$ 的状态通过后缀链接进行遍历。对于每一个状态，我们尝试添加一个通过字符 $c$ 到新状态 $\textit{cur}$ 的转移。然而我们只能添加与原有转移不冲突的转移。因此我们只要找到已存在的 $c$ 的转移，我们就必须停止。
最简单的情况是我们到达了虚拟状态 $-1$ ，这意味着我们为所有 $s$ 的后缀添加了 $c$ 的转移。这也意味着，字符 $c$ 从未在字符串 $s$ 中出现过。因此 $\textit{cur}$ 的后缀链接为状态 $0$ 。
第二种情况下，我们找到了现有的转移 $(p,q)$ 。这意味着我们尝试向自动机内添加一个 已经存在的 字符串 $x+c$ （其中 $x$ 为 $s$ 的一个后缀，且字符串 $x+c$ 已经作为 $s$ 的一个子串出现过了）。因为我们假设字符串 $s$ 的自动机的构造是正确的，我们不应该在这里添加一个新的转移。然而，难点在于，从状态 $\textit{cur}$ 出发的后缀链接应该连接到哪个状态呢？我们要把后缀链接连到一个状态上，且其中最长的一个字符串恰好是 $x+c$ ，即这个状态的 $\operatorname{len}$ 应该是 $\operatorname{len}(p)+1$ 。然而还不存在这样的状态，即 $\operatorname{len}(q)>\operatorname{len}(p)+1$ 。这种情况下，我们必须通过拆开状态 $q$ 来创建一个这样的状态。
如果转移 $(p,\,q)$ 是连续的，那么 $\operatorname{len}(q)=\operatorname{len}(p)+1$ 。在这种情况下一切都很简单。我们只需要将 $\textit{cur}$ 的后缀链接指向状态 $q$ 。
否则转移是不连续的，即 $\operatorname{len}(q)>\operatorname{len}(p)+1$ ，这意味着状态 $q$ 不只对应于长度为 $\operatorname{len}(p)+1$ 的后缀 $s+c$ ，还对应于 $s$ 的更长的子串。除了将状态 $q$ 拆成两个子状态以外我们别无他法，所以第一个子状态的长度就是 $\operatorname{len}(p)+1$ 了。
我们如何拆开一个状态呢？我们复制状态 $q$ ，产生一个状态 $\textit{clone}$ ，我们将 $\operatorname{len}(\textit{clone})$ 赋值为 $\operatorname{len}(p)+1$ 。由于我们不想改变遍历到 $q$ 的路径，我们将 $q$ 的所有转移复制到 $\textit{clone}$ 。我们也将从 $\textit{clone}$ 出发的后缀链接设置为 $q$ 的后缀链接的目标，并设置 $q$ 的后缀链接为 $\textit{clone}$ 。
在拆开状态后，我们将从 $\textit{cur}$ 出发的后缀链接设置为 $\textit{clone}$ 。
最后一步我们将一些到 $q$ 转移重定向到 $\textit{clone}$ 。我们需要修改哪些转移呢？只重定向相当于所有字符串 $w+c$ （其中 $w$ 是 $p$ 的最长字符串）的后缀就够了。即，我们需要继续沿着后缀链接遍历，从结点 $p$ 直到虚拟状态 $-1$ 或者是转移到不是状态 $q$ 的一个转移。

根据上面的构造方法，我们还能证明，自动机中的节点数的量级为 $O(n)$ 级别的。

构建方法

inline void extend(char *s)
{
    int n = strlen(s + 1);
    for(int i = 1; i <= n; i ++ )
    {
        int p = last, cur = ++ idx, c = s[i] - 'a';
        f[cur] = siz[cur] = 1;
        len[cur] = len[p] + 1;
        while(p != -1 && !tr[p][c])
        {
            tr[p][c] = cur;
            p = link[p];
        }
        if(p == -1) link[cur] = 0;
        else
        {
            int q = tr[p][c];
            if(len[q] == len[p] + 1) link[cur] = q;
            else
            {
                int copy = ++ idx;
                len[copy] = len[p] + 1;
                link[copy] = link[q];
                for(int i = 0; i < 26; i ++ ) tr[copy][i] = tr[q][i];
                while(p != -1 && tr[p][c] == q)
                {
                    tr[p][c] = copy;
                    p = link[p];
                }
                link[cur] = link[q] = copy;
            }
        } 
        last = cur;
    }

    for(int i = 1; i <= idx; i ++ ) G[link[i]].emplace_back(i);
}

注意：SAM 中节点数最多能够达到 $2n-1$ ，因此需要将数组开两倍。

一些题目

【模板】后缀自动机（SAM）

给定一个只包含小写字母的字符串 $S$ ，求出 $S$ 的所有出现次数不为 $1$ 的子串的出现次数乘上该子串长度的最大值。

数据范围： $|S| \le 10^6$ 。

模板题。我们先建出 SAM，然后在 Parent Tree 上进行 DP。 $u$ 节点代表的字符串出现的次数就是它在 Parent Tree 上子树的大小。因此直接统计即可。

时间复杂度 $O(n)$ 。

[JSOI2012] 玄武密码

给定 $n$ 个字符串 $t$ ，对于每一段字符串 $t$ ，求出其最长的前缀 $p$ ，满足 $p$ 是 $s$ 的子串。

数据范围： $|s|\le 10^7, \sum |t|\le 10^7$ ，字符集大小为 $4$ 。

SAM 裸题。由于 SAM 上存储了所有后缀的前缀，因此我们直接把 $t$ 放到 SAM 上跑即可，跑了多长不能跑了就为答案。

时间复杂度 $O(n)$ 。

[TJOI2015] 弦论

对于一个给定的长度为 $n$ 的字符串，求出它的第 $k$ 小子串。

这里有两种询问：不同位置的相同子串算作一个和不同位置的相同子串算作多个。

数据范围： $n\le 10^5$ 。

大杂烩题目，感觉像两道题拼起来的。

我们先考虑不同位置相同子串算一个的情况。这时我们可以先 dp，由于 SAM 为一张 DAG，因此我们可以记录从某个点开始走一共会走出多少种字符串。然后输出方案时，我们从小到大遍历出边，同时减去走这条边的方案数。直到 $k$ 小于走这条边的方案数就走这条边。

而对于不同位置算多个的，我们可以先按照上面模板题的思路，先统计出每个点出现的次数，然后按照上面的重新 dp 即可。

Longest Common Substring

输入两个字符串，输出它们的最长公共子串长度。

数据范围： $|s|, |t|\le 2.5\times 10^5$ 。

我们先对一个串建 SAM，然后把另一个串放到 SAM 上跑。由于后缀链接记录的是前缀的后缀，因此跑不了的时候我们就一直跳后缀链接，同时记录一个最大长度即可。

时间复杂度 $O(n)$ 。

[AHOI2013] 差异

给定一个长度为 $n$ 的字符串 $S$ ，令 $T_i$ 表示它从第 $i$ 个字符开始的后缀。求

\sum_{1\leqslant i<j\leqslant n}\mathrm{len}(T_i)+\mathrm{len}(T_j)-2\times\mathrm{lcp}(T_i,T_j)

数据范围： $n\le 5\times 10^5$ 。

前面两项好搞，我们先提出来。这样我们的目标就变为了求 $\sum_{1\leqslant i<j\leqslant n}\mathrm{lcp}(T_i,T_j)$ 。

lcp 不好求，但是 SAM 适合求 lcs，我们就把字符串翻转过来，就变成了求 lcs。一个结论： $i$ 前缀和 $j$ 前缀的 lcs 即为在 Parent Tree 上的 $lca$ 的 $\mathrm{len}$ 。因此我们可以直接树形 dp，对于每个点算一下有多少对点的 $lca$ 是它即可。

时间复杂度 $O(n)$ 。

Yet Another LCP Problem

给定一个字符串，每次询问的时候给出两个正整数集合 $A$ 和 $B$ ，求 $\sum_{i \in A,j \in B}lcp(i,j)$

数据范围： $|s|\le 2\times 10^5, \sum |A|, \sum |B|\le 2\times 10^5$ 。

我们先把字符串翻转，将 $lcp$ 转化为 $lcs$ 。根据上一道题的套路，我们建出来 SAM，这样两个点在 parent tree 上对应的 lca 的 $len$ 即为最长公共后缀。

但是这里有多组询问，我们就可以每组询问建虚树，然后在虚树上进行 dp 计算答案。具体的说，我们设 $sum_{u, 0}$ 为 $u$ 子树中 $A$ 集合点的数量， $sum_{u, 1}$ 为 $u$ 子树中 $B$ 集合点的数量。通过容斥我们就能算出有多少 $a\in A, b\in B$ 的 lca 是 $u$ 。最终再乘上 $len_u$ 即可。

时间复杂度 $O(n\log n)$ 。

[NOI2018] 你的名字

给定一个字符串 $S$ ，多次询问。询问给定一个字符串 $T$ ，有多少 $T$ 的子串满足其不为 $S[l\sim r]$ 构成的字符串的子串。

数据范围： $|S|\le 5\times 10^5, \sum |T|\le 10^6$

我们先考虑 $L=1, R = |S|$ 的情况。这时我们对 $S$ 和 $T$ 分别建 SAM，对 $T$ 的第 $i$ 个前缀，我们要找出它最长的后缀且这个后缀是 $S$ 的子串。我们加入 $T$ 的第 $i$ 个字符后，我们看当前节点是否有这一个转移，如果没有就一直跳 $link$ 。

最后我们将每一个前缀的满足上面要求的最长后缀记录为 $lim_i$ 。我们再设 SAM 上第 $i$ 个节点对应字符串中的位置是 $tag_i$ 。那么最后的答案就是：

\sum \limits_{p=1}^{idx}\max(0, \mathrm{len}(p)-\max(\mathrm{len}(\mathrm{link}(p)), lim_{tag_p}))

也就是对于每个节点，我们用它的长度减去它匹配的长度就是它不为 $S$ 子串的长度。

而对于有了区间限制这个东西，我们可以思考一下我们上面用 SAM 都做了什么：跳 $link$ 和看是否有转移。我们可以直接用线段树维护每个点的 $\mathrm{endpos}$ 集合。当这个集合中有我们限制的区间之内的位置，我们才可以进行转移，否则就跳出了这个区间。

而对于 $\mathrm{endpos}$ ，在 parent tree 上是父亲包含儿子的关系，因此我们直接线段树合并维护一下就好了。

时间复杂度 $O(n\log n)$ 。

区间本质不同子串个数

给定一个长度为 $n$ 的字符串 $S$ ， $m$ 次询问由 $S$ 的第 $L$ 到第 $R$ 个字符组成的字符串包含多少个本质不同的子串。

数据范围： $n\le 10^5, m\le 2\times 10^5$ 。

对于区间数不同颜色这种问题，一个常见的套路为讲询问离线，然后右端点扫描线，同时只维护每个不同元素在最右端出现的位置。

而对于这题我们也可以这么做。我们把询问离线后做扫描线，发现每次新加入的元素的 $\mathrm{endpos}$ 都包含新加入的右端点，也就是都是以右端点为结尾的子串。可以发现这些字符串在 parent tree 上对应着到根的一条链，于是我们的任务就变成了把这条链上的原来的影响消除，并且把它们在新位置的贡献加上。

我们就可以沿用[SDOI2017] 树点涂色的套路，用 LCT 来维护这个过程。具体地说，我们在 LCT 的每个点维护一个 $val$ ，表示它目前 $\mathrm{endpos}$ 的最大值。每次 access 时我们把一整条链的影响全部消除，同时把最终这条实链的 $val$ 全部覆盖为当前的右端点。然后我们再把当前新增加的字符串的开始位置加上即可。