算法竞赛学习笔记

写写 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}$，有很多性质，这里不再一一证明，仅罗列在下面：

  1. 当 $\mathrm{Endpos}(a)=\mathrm{Endpos}(b), |a|<|b|$ 时，在 $t$ 中每次出现时，$a$ 都作为 $b$ 的后缀出现。
  2. 两个字符串 $a, b$（假设 $|a|<|b|$），要么 $\mathrm{Endpos}(a) \cup \mathrm{Endpos}(b) = \varnothing$，要么 $\mathrm{Endpos}(b) \subseteq \mathrm{Endpos}(a)$
  3. 对于同一 $\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)$ 级别的。

构建方法 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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$ 全部覆盖为当前的右端点。然后我们再把当前新增加的字符串的开始位置加上即可。

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

说着很麻烦但是写起来都是板子反而相当好写/yiw

The End

其实 SAM 还有很多东西没讲完，但是限于作者本人能力问题，有很多应用和证明都没有讲。以后可能会再更新一点。

参考资料：OIWIKI -https://oi-wiki.org/string/sam/