1 概述及定义
后缀自动机（SAM）是一个强有力的数据结构，可以解决很多经典字符串问题，例如：
- 线性复杂度进行字符串匹配。
- 线性复杂度求出一个字符串的所有不同子串个数。
那么我们定义一个字符串 \(S\) 的 SAM 是一个可以接受 \(S\) 所有后缀的最小 DFA（确定性有限状态自动机）。
也就是说，SAM 存储的是字符串 \(S\) 的所有后缀信息。而严谨的讲，上面那句话的意思如下：
- SAM 是一张 DAG，节点被称为状态，边称为转移。每个转移上标有字母，每个节点出发的转移都不同。
- SAM 存在一个源点 \(t_0\)，其他所有节点都可由 \(t_0\) 走到。
- 存在一个或多个终止状态，如果从 \(t_0\) 出发，走到一个终止状态，走过的转移连起来一定是 \(S\) 的一个后缀；同时，\(S\) 的所有后缀都可以用 \(t_0\) 到终止状态的路径描述。
当然只有这三条是不够的。如果只有这三条，我建一颗包含 \(S\) 所有后缀的 Trie 树也可以叫 SAM 了。所以还有一条：
- SAM 是满足上述条件的自动机中，节点数量最少的。
由于其存储的是所有后缀，所以查询子串信息需要看后缀的前缀。放到 SAM 上讲，从 \(t_0\) 开始出发的任意一条路径对应这 \(S\) 中的一个子串；反过来，\(S\) 中的所有子串都对应从 \(t_0\) 开始出发的任意一条路径。因此 SAM 存储的其实不仅是后缀信息，而是所有子串信息。
下面举一个例子，对于字符串 abbb，其 SAM 如下（绿色节点为终止状态）：
最后一点，SAM 的强大之处不仅在于它存储了所有子串的信息，还在于它存储这些信息的空间复杂度仅仅是 \(O(n)\)，构建的复杂度也是 \(O(n)\)。
2 parent 树
显然在上面的说法中，我们可以求出每一个子串，却无法确定这个子串的其他信息：位置、长度等。因此我们需要引入一个新的结构——parent 树来统计子串信息。
parent 树是 SAM 的一部分，类比的话就相当于 AC 自动机中的 fail 树。而这也能说明 parent 树的重要地位，实际上，大多数 SAM 的题都是基于 parent 树的性质来做的。
2.1 结束位置 endpos 与 endpos 等价类
2.1.1 定义与实际意义
考虑一个字符串 \(S\) 的任意子串 \(s\)，我们记 \(\text{endpos}(t)\) 表示 \(s\) 在 \(S\) 中每次出现的结束位置。例如对于 \(S=\) abcbc，子串 bc 的 \(\text{endpos}\) 就是 \(\{2,4\}\)。
而对于两个子串 \(s_1,s_2\)，它们的 \(\text{endpos}\) 集合可能是相等的。例如上面例子中子串 bc 和 c 的 \(\text{endpos}\) 集合都是 \(\{2,4\}\)。由此我们可以将 \(S\) 的所有子串根据 \(\text{endpos}\) 分成若干个等价类。我们定义一个 \(\text{endpos}\) 等价类记作 \(E\)，其对应的字符串集合为 \(\text{endpos}(E)\)，当中第 \(i\) 个字符串为 \(E_i\)。
现在考虑回到 SAM 上来，如果我们求出了子串 \(s\) 的 \(\text{endpos}\)，那么当我们在 SAM 上找到这个子串时，就可以知道它在哪出现过、出现了多少次。这样我们就补充了上面 SAM 遗漏的子串信息。
同时，SAM 中的每一个状态都对应着一个或多个 \(\text{endpos}\) 相同的子串。也就是说，SAM 上每一个节点 \(x\) 都对应一个 \(\text{endpos}\) 等价类，而这个等价类的大小就是从 \(t_0\) 出发走到 \(x\) 的路径条数之和。
下面我们会运用 \(\text{endpos}\) 的性质来构建 SAM，但是我们还需要一些引理。
2.1.2 相关引理和证明
引理 \(1\)：对于字符串的两个非空子串 \(s_1,s_2\)（令 \(|s_1|\ge |s_2|\)）的 \(\text{endpos}\) 相同，当且仅当 \(s_2\) 每一次在 \(S\) 中出现都以 \(s_1\) 的后缀形式出现。
证明：
先证 \(\Rightarrow\)。由于两者 \(\text{endpos}\) 相同，那么说明它们都是在几个相同位置的长度不同的后缀。又由于 \(|s_1|\ge|s_2|\)，所以 \(s_2\) 每一次出现都以 \(s_1\) 的后缀形式出现。
再证 \(\Leftarrow\)。由于 \(s_2\) 每次出现都以 \(s_1\) 的后缀形式出现，说明两者的结束位置一定相同，即两者 \(\text{endpos}\) 相同。
引理 \(2\)：对于字符串的两个非空子串 \(s_1,s_2\)（令 \(|s_1|\ge |s_2|\)），若 \(s_2\) 是 \(s_1\) 后缀，则 \(\text{endpos}(s_1)\subseteq \text{endpos}(s_2)\)；否则 \(\text{endpos}(s_1)\cap \text{endpos}(s_2)=\varnothing\)。
证明：
-
由于 \(s_2\) 是 \(s_1\) 的后缀，那么 \(s_1\) 出现时 \(s_2\) 必然出现；但是 \(s_2\) 出现时 \(s_1\) 未必出现，于是就得到 \(\text{endpos}(s_2)\) 包含 \(\text{endpos}(s_1)\)。
-
设 \(\text{endpos}(s_1)\) 与 \(\text{endpos}(s_2)\) 有相同元素，则代表此时 \(s_1,s_2\) 同时出现。又由于 \(|s_1|\ge|s_2|\)，那么自然就得到 \(s_2\) 是 \(s_1\) 后缀，与题意矛盾！因此两个集合不可能有相同元素，即交集为空集。
引理 \(3\)：对于一个 \(\text{endpos}\) 等价类当中的任意两子串，较短者一定是较长者的后缀。
证明：
显然任意两子串的 \(\text{endpos}\) 相同，由引理 \(1\) 可得，两个子串中较短者每一次都以较长者的后缀形式出现。也就是说较短者一定是较长者的后缀。
引理 \(4\)：设 \(l,r\) 分别为一个 \(\text{endpos}\) 等价类 \(E\) 中最短和最长子串的长度。则 \(\bigcup|E_i|=\{l\le x\le r,x\in \mathbb{N}^*\}\)。
证明：
考虑等价类中最短的字符串 \(s_1\) 和最长的字符串 \(s_2\)。由引理 \(1\) 得，\(s_1\) 每一次在 \(S\) 中出现都以 \(s_2\) 的后缀形式出现。
现在考虑 \(s_2\) 的任意一个后缀 \(s\)，满足 \(|s_1|\le|s|\le|s_2|\)。那么显然 \(s_2\) 每次出现都会伴随着 \(s\) 出现，\(s\) 出现会伴随着 \(s_1\) 出现。又由于 \(s_1\) 和 \(s_2\) 的出现位置是相同的，那么自然 \(s\) 的出现位置与 \(s_1,s_2\) 都相同，即 \(s\) 的 \(\text{endpos}\) 与 \(s_1,s_2\) 的 \(\text{endpos}\) 相同，于是 \(s\) 就属于这个 \(\text{endpos}\) 等价类 \(E\)。
于是任意长度在 \([l,r]\) 之间的后缀 \(s\) 都属于该 \(\text{endpos}\) 等价类，即该等价类满足 \(\bigcup|E_i|=\{l\le x\le r,x\in \mathbb{N}^*\}\)。
2.2 后缀链接 link 和 parent 树
2.2.1 后缀链接 link
考虑 SAM 中某个不是 \(t_0\) 的状态 \(v\)。我们已经知道，\(v\) 会对应一个 \(\text{endpos}\) 等价类。如果定义 \(S\) 为这些字符串中最长的，则当中其他所有字符串都是 \(S\) 的后缀（引理 \(3\)）。
我们还知道字符串 \(S\) 的后缀按长度排序后，前面几个都包含于这个等价类（引理 \(4\)），且所有其它后缀都在其它等价类中。我们记 \(t\) 为最长的这样的后缀，将 \(v\) 连到 \(t\) 代表的等价类节点上，这就是 \(v\) 的后缀链接。
形式的讲，后缀链接 \(\text{link}(v)\) 连接到 \(S\) 的在另一个 \(\text{endpos}\) 等价类的最长后缀，其等价类对应的状态。
此时根据引理 \(4\)，从某个等价类 \(E\) 开始不断跳 \(\text{link}\) 直到初始节点 \(t_0\)，就可以访问 \(S\) 的所有后缀。这时候应该要敏锐的发现，所有的 \(\text{link}\) 似乎可以构成一种结构，于是有了下面的结论：
引理 \(4\)：所有 \(\text{link}\) 构成一颗根节点为 \(t_0\) 的树。
2.2.2 parent 树
首先先给出 parent 树的定义：通过 \(\text{endpos}\) 集合构建的树，满足每个子节点的集合都包含在父节点的集合中。由引理 \(2\) 可得，两个 \(\text{endpos}\) 集合要么一个包含另一个，要么完全没有交集，因此按照上面的构造方式一定可以构造出一颗树。
那么为什么将 \(\text{link}\) 和 parent 树放在一起呢？实际上你可能已经猜到了。
引理 \(5\)：由 \(\text{link}\) 构成的树与 parent 树相同。
首先考虑一个不是 \(t_0\) 的状态 \(v\)，以及它的后缀链接 \(\text{link}(v)\)。由引理 \(2\) 及后缀链接定义可得，\(\text{endpos}(v)\varsubsetneq \text{endpos}(\text{link}(v))\)。
注意这里的 \(\varsubsetneq\) 表示后面的集合至少有一个不属于前面的集合。首先由引理 \(2\) 可得 \(\text{endpos}(v)\subseteq \text{endpos}(\text{link}(v))\)，但是若 \(\text{endpos}(v)= \text{endpos}(\text{link}(v))\)，这两个节点就应该被合并成一个节点了，所以需要使用 \(\varsubsetneq\)。
然后再根据 parent 树的定义，我们就可以发现这与定义完全一致。所以 parent 树就是 \(\text{link}\) 构成的树。
最后给出一个例子，对于字符串 abcbc，构建的 DAG 和 parent 树分别如下（绿色节点为终止状态）：
所以最后通过这么一番倒腾，我们就弄出了 parent 树需要的所有东西。接下来我们将它们整合一下，准备开始构造 SAM。
2.3 小结
我们对上面 2.1、2.2 小节的内容进行整理，为后面的构建进行铺垫。
- \(S\) 的子串看可以根据 \(\text{endpos}\) 划分为若干等价类。
- SAM 由初始状态 \(t_0\) 和与每一个 \(\text{endpos}\) 等价类对应的状态组成。
- 对于每一个状态 \(v\)，有一个或多个子串与之对应。我们记 \(\text{lest}(v)\) 表示其中最长的字符串，用 \(\text{maxl(v)}\) 表示其长度。类似的，使用 \(\text{sest}(v)\) 表示其中最短的字符串，长度为 \(\text{minl}(v)\)；
- 于是这个状态中所有的字符串都是 \(\text{lest}(v)\) 的不同后缀，且所有字符串长度覆盖区间 \([\text{minl}(v),\text{maxl}(v)]\)。
- 对于状态 \(v\)，定义后缀链接 \(\text{link(v)}\) 表示连接到对应字符串 \(\text{lest}(v)\) 的长度为 \(\text{minl}(v)-1\) 的后缀的等价类状态。所有后缀链接可以构成一棵树，且与 parent 树相同。
- 对于状态 \(v\)，显然会有如下式子：\(\text{minl}(v)=\text{maxl}(\text{lenk}(v))+1\)。
- 从任意状态 \(v\) 开始跳后缀链接，总会到达初始状态 \(t_0\)，且走到的所有状态对应的所有后缀长度正好覆盖 \([0,\text{maxl(v)}]\)。
3 构建 SAM
3.1 流程
与 PAM 等自动机一致，SAM 也是用增量的构建方式，即逐个加入字符维护。
一开始 SAM 只有一个状态 \(t_0\)，编号为 \(0\)。我们令它的 \(\text{maxl}=0,\text{link}=-1\)。
现在考虑给当前字符串添加字符 \(c\)。令 \(last\) 为添加字符 \(c\) 之前，整个字符串对应的状态。
创建一个新的状态 \(cur\)，令 \(\text{maxl}(cur)=\text{maxl}(last)+1\)。现在我们从状态 \(lst\) 开始跳后缀链接，如果没有字符 \(c\) 的转移，创建一条到 \(cur\) 的字符 \(c\) 的转移；否则我们将这个状态标记为 \(p\)，并停止跳后缀链接。
如果我们没有找到 \(p\)，意味着它的 \(\text{endpos}\) 集合不属于之前任意一个 \(\text{endpos}\) 集合，于是令 \(\text{link}(cur)=0\) 并结束。
否则这个 \(p\) 就会有一个 \(c\) 的转移，我们将这个转移出去的点记作 \(q\)。若 \(\text{maxl(p)}+1=\text{maxl}(q)\)，那么直接令 \(\text{link(cur)}=q\) 即可。这一步与其它自动机的连边思路基本一致，通过相同的转移 \(c\) 来找后缀链接。
真正麻烦的地方在于 \(\text{maxl}(p)+1\neq \text{maxl}(q)\) 的时候。这时我们需要复制状态 \(q\)，称这个复制的状态为 \(q'\)，它需要保留 \(q\) 除了 \(\text{maxl}\) 以外的所有信息（即后缀链接与转移），将 \(\text{maxl}(q')\) 设为 \(\text{maxl}(p)+1\)。接下来我们将 \(q\) 和 \(cur\) 的 \(\text{link}\) 全部指向 \(q'\)。
最后我们再从 \(p\) 开始跳后缀链接，如果有状态 \(v\) 有字符 \(c\) 的转移且转移到了 \(q\)，将 \(v\to q\) 的转移重定向到 \(v\to q'\) 的转移。直到跳到 \(-1\) 或找不到通过 \(c\) 转移到 \(q\) 就停止。
通过上面三种情况的分析，我们就成功加入了这个字符 \(c\)。最后将 \(last\) 设为 \(cur\) 即可。
当然我们会发现上面的过程中没有提到终止状态。实际上，我们在整个字符串建立好 SAM 之后找到整个字符串对应的状态（此时存储在 \(last\) 中），然后开始跳它的后缀链接。容易发现，这样跳到的所有状态都代表整个字符串的后缀，将它们标记为终止状态即可。
3.2 正确性说明
说实话，这一部分并不重要，但是里面还有一些有趣的内容，所以我择出来一些写上去。
首先对于前两种情况，正确性都比较明晰，上文已经提到，不再赘述。
我们着重来看一下 \(\text{maxl}(p)+1\neq \text{maxl}(q)\)，其实这就意味着 \(\text{maxl}(p)+1<\text{maxl}(q)\)。也就是说状态 \(q\) 不止对应长度为 \(\text{maxl}(p)+1\) 的后缀，还对应更长的子串。因此我们考虑将状态 \(q\) 拆成两个状态，同时第一个状态的 \(\text{maxl}\) 就是 \(\text{maxl}(p)+1\)。这就是上面提到的“复制”出的状态 \(q'\)。
那么自然的，这个 \(q'\) 就要继承 \(q\) 的所有信息，同时只有 \(\text{maxl}\) 需要改变。最后我们希望将一些到 \(q\) 的转移重定向到 \(q'\)，那么只需要重定向字符串 \(\text{lest}(p)+c\) 的所有后缀即可，因为只有它们是在 \(q'\) 的 \(\text{endpos}\) 等价类中的。
既然这样我们就直接跳 \(p\) 的 \(\text{link}\)，然后看有没有 \(c\) 的转移指向 \(q\)。有的话就说明这个状态中的字符串加上 \(c\) 构成了 \(q'\) 中的串，因此需要重定向。而如果找到第一个有 \(c\) 的转移却不指向 \(q\) 的，则该状态无需重定向，同时它的后缀也无需重定向，此时直接跳出即可。
3.3 时空复杂度说明
事实上，SAM 复杂度是线性的先决条件是字符集大小 \(|\sum|\) 为常数。若 \(|\sum|\) 不为常数，则 SAM 的空间复杂度会退化为 \(O(n|\sum|)\)。此时可以利用 map 进行操作，将空间降至 \(O(n)\)，但相应的代价是时间复杂度上升为 \(O(n\log |\sum|)\)。
3.4 代码
整体来讲 SAM 的代码实现并不复杂，只要按照上面的思路走就行。基础的 SAM 封装如下：
struct SAM {
int tot, lst;
//点数，上一个位置对应状态
struct node {
int len, link, son[26];
//maxl(v),link(v)，以及转移
}sam[Maxn];
void init() {//初始化
for(int i = 0; i <= tot; i++) {
sam[i].len = sam[i].link = 0;
memset(sam[i].son, 0, sizeof sam[i].son);
}
sam[0].link = -1;
lst = tot = 0;
}
void insert(int i) {
sam[++tot].len = sam[lst].len + 1;//新建状态
int pos = lst, ch = s[i] - 'a';
lst = tot;
while(pos != -1 && sam[pos].son[ch] == 0) {//跳后缀链接
sam[pos].son[ch] = tot;
pos = sam[pos].link;
}
if(pos == -1) sam[tot].link = 0;
else {
int p = pos, q = sam[pos].son[ch];
if(sam[p].len + 1 == sam[q].len) {
sam[tot].link = q;
}
else {
sam[++tot] = sam[q];//复制 q 状态
sam[tot].len = sam[p].len + 1;
sam[tot - 1].link = sam[q].link = tot;
while(pos != -1 && sam[pos].son[ch] == q) {//跳后缀链接
sam[pos].son[ch] = tot;//重定向
pos = sam[pos].link;
}
}
}
}
}SAM;