SAM（后缀自动机）学习笔记

后缀树（数据结构）和本文中的后缀树其实不是一个东西，更规范的叫法应该是 parent 树，但是由于 $S$ 的后缀树就是其反串的 parent 树，所以并没有加以区分。

前言

SAM（后缀自动机） 是一种强大的数据结构，在应用上可以完全包含 SA（后缀数组），往往比 SA 好写好调且时间复杂度更优。

本文借鉴了 后缀自动机(SAM)奶妈式教程 - 一铭君一 - 博客园 (cnblogs.com)（算法思想、实现、技巧）和 后缀自动机 - star_road_xyz - 博客园 (cnblogs.com)（状态个数、转移个数证明）。

为了表述方便，这里为本文规定一些记号：

• $|S|$：字符串 $S$ 的长度；
• $V$：字符集大小；

基本定义

1. SAM 是一个 DAG，它的节点被称作“状态”，边被称作“转移”；
2. SAM 有一个初始状态 $rt$（代表空串），所有其它状态都能通过转移从 $rt$ 到达；
3. 每个转移会被标记上字符集中的一个字符（类似边权），从一个状态出发的所有转移的字符互不相同；
4. 存在至少一个终止状态，从 $rt$ 出发到终止状态的每一条路径上的所有转移依次拼接得到的字符串都是原串的后缀，也就是说原串的每个后缀都能表示成从 $rt$ 到终止状态的路径；
5. SAM 是满足上述条件中状态数最少的 DAG；

一些记号

• $S$：要被建 SAM 的原串；

• $rt$：SAM 的初始状态（空串对应状态）；

• $to_{u,ch}$ 从状态 $u$ 出发的，被标记上字符 $ch$ 的转移；

SAM 的优势

不难发现，从 $rt$ 到SAM 上的每个状态路径上的字符拼接起来都是原串某个后缀的一个前缀，这意味着原串的每个子串都能表示成从 $rt$ 到某个状态的路径。

虽然大多数 SAM 能做的操作 SA 也能做，但是线性 SA 的 DC3 算法常数巨大，并且 SA 性质较少，应用时通常需要一些较为复杂的数据结构辅助，这些数据结构相应也会提高时间复杂度。但建立字符串 $S$ 对应的 SAM 的时空复杂度仅为 $O(|S|)$，并且 SAM 有着更好的性质。

综上，SAM 不失为一种十分优秀的字符串算法。

$\operatorname{endpos}$ 和 $\operatorname{endpos}$ 等价类

使用 $\operatorname{endpos}$ 等价类压缩时空就是 SAM 保持优秀时间复杂度的原因。

记 $\operatorname{endpos}(s)$ 表示 $s$ 在 $S$ 中每次出现的结尾位置的集合（下标从 $1$ 开始），例如：

S: abab
s:           a    b,ab   ba,aba  bab,abab
endpos(s): {1,3}  {2,4}   {3}       {4}

不难发现，某些字符串的 $\operatorname{endpos}$ 是相同的，例如例子中的 b 和 ab。那么不妨将所有 $\operatorname{endpos}(s)=A$ 的归到同一个等价类中，记 $\operatorname{endpos'}(A)=\{s|\operatorname{endpos(s)=A}\}$。

在 SAM 中，一个状态表示的并不是具体的某个字符串，而是一个等价类。

一些记号：

• $\operatorname{endpos}(s)$：$s$ 在 $S$ 中每次出现的结尾位置的集合（下标从 $1$ 开始）；
• $\operatorname{endpos'}(A)$：$\{s|\operatorname{endpos(s)=A}\}$ 即 $\operatorname{endpos}(s)=A$ 的 $s$ 构成的集合；
• $E(u)$：状态 $u$ 代表的等价类；
• $\operatorname{sta}(s)$：字符串 $s$ 所属的等价类对应的状态；

$\operatorname{endpos}$ 等价类的一些性质

引理 1

考虑两个非空字符串 $s1,s2$，满足 $|s1|\ge|s2|$。

1. 若 $\operatorname{endpos}(s1)=\operatorname{endpos}(s2)$，则 $s2$ 是 $s1$ 的后缀，且 $s2$ 在且仅在 $s1$ 在 $S$ 中出现时作为它的后缀出现；

2. 若 $s2$ 是 $s1$ 的后缀，且 $s2$ 在且仅在 $s1$ 在 $S$ 中出现时作为它的后缀出现，那么 $\operatorname{endpos}(s1)=\operatorname{endpos}(s2)$；

证明是显然的。

引理 2

考虑两个非空字符串 $s1,s2$，满足 $|s1|\ge|s2|$。

1. 若 $s2$ 是 $s1$ 的后缀，那么 $\operatorname{endpos}(s1)\subseteq\operatorname{endpos}(s2)$；

2. 若 $s2$ 不是 $s1$ 的后缀，那么 $\operatorname{endpos}(s2)\cap\operatorname{endpos}(s1)=\varnothing$；

第一条是因为 $s1$ 每次出现 $s2$ 都必然会出现。

第二条是因为若 $s2$ 是 $s1$ 的子串且存在 $p$ 满足 $p\in \operatorname{endpos}(s1)$ 且 $p\in \operatorname{endpos}(s2)$ 则 $s1$ 和 $s2$ 都一定会在 $p$ 处结束，$s2$ 必定是 $s1$ 的子串，和假设矛盾，得证。

引理 3

考虑一个 $\operatorname{endpos}$ 等价类 $A=\operatorname{endpos}'(E)$。

1. $A$ 中不包含两个长度相同但本质不同的字符串；
2. 对于 $A$ 中任意两个字符串，短的那个一定是长的那个的真后缀，也就是说 $A$ 中所有字符串都是最长的那个的后缀；
3. 设 $l,r$ 分别为 $A$ 中最短和最长的字符串的长度，则 $\{|s|,s\in A\}=[l,r]\cap \mathbb{N}^+$，即 $l,r$ 之间的每种长度的串都会出现恰好一次；

第一条可以由引理 1 推出，第二条可以由引理 2 推出，考虑第三条的证明。

不难发现只有可能是等号右边的集合的某个元素没在等号左边的集合中出现。那么设 $d\in ([l,r]\cap \mathbb{N}^+)$ 且 $d\notin\{|s|,s\in A\}$。由于第二条，所以可以设长度为 $d$ 的字符串为 $s^d$，则由于引理 2，有 $A\subseteq\operatorname{endpos}(s^d)$。

此时若 $A\subset \operatorname{endpos}(s^d)$，则 $s^d$ 的所有子串的 $\operatorname{endpos}$ 都会不等于 $A$。由于第二条，$t\in ([l,d]\cap\mathbb{N^+})$ 的所有 $t$ 均满足 $A\subset \operatorname{endpos(s^t)}$，那么 $l$ 将会等于 $d+1$，和 $d\in ([l,r]\cap \mathbb{N}^+)$ 矛盾，得证。

一些记号：

• $\operatorname{long}(u)$：$\operatorname{endpos}'(\operatorname{E}(u))$ 中最长的字符串；
• $\operatorname{len(u)}$：$|\operatorname{long}(\operatorname{E}(u))|$ 即 $\operatorname{endpos}'(\operatorname{E}(u))$ 中最长的字符串的长度；
• $\operatorname{short}(u)$：$\operatorname{endpos}'(\operatorname{E}(u))$ 中最短的字符串；
• $\operatorname{slen(u)}$：$|\operatorname{short}(\operatorname{E}(u))|$ 即 $\operatorname{endpos}'(\operatorname{E}(u))$ 中最短的字符串的长度；

后缀指针 $\operatorname{link}$ 和后缀树

设 $A=E(u)$ 即状态 $u$ 代表的等价类，$w$ 为 $\operatorname{long}(u)$ 最长的满足 $w\notin A$ 的一个后缀，$v$ 为 $\operatorname{sta}(w)$ 即 $w$ 所属等价类对应的状态（由 SAM 的定义可知这个状态一定存在），$\operatorname{link}(u)$ 即为 $v$。特别的，$rt$ 没有 $\operatorname{link}$ 指针。

根据引理 3，从状态 $u$ 出发不断跳 $\operatorname{link}$ 到 $rt$ 路径上所有状态的等价类并起来就是 $\operatorname{long}(u)$ 的所有后缀，所以 $\operatorname{link}$ 也叫后缀指针。

引理 5

对于一个状态 $u$，设 $\operatorname{link}(u)=v$。

1. $\operatorname{long}(v)$ 是 $\operatorname{short}(u)$ 的长度为 $\operatorname{slen}(u)-1$ 的后缀；
2. $\operatorname{E}(u)\subsetneq \operatorname{E}(v)$；

第一条可以由引理 3 得出，第二条可以由引理 2 和 $\operatorname{link}$ 指针的定义得出。

需要注意的是，利用这个引理，SAM 中的每个状态便只需要记录等价类中的最长串。

引理 6

把状态看作节点，则所有有向边 $u\to\operatorname{link(u)}$ 构成一棵以 $rt$ 为根的内向树（后缀树）。

首先由于所有状态不断跳 $\operatorname{link}$ 总能跳回 $rt$（空串是所有字符串的后缀），所以“后缀图”一定连通。

然后由于只有 $rt$ 没有 $\operatorname{link}$ 指针，所以“后缀图”的边数恰好等于点数减 $1$，所以“后缀图”是一棵树。

一些记号：

• $\operatorname{link}(u)$：设 $A=E(u)$ 即状态 $u$ 代表的等价类，$w$ 为 $\operatorname{long}(A)$ 最长的满足 $w\notin A$ 的一个后缀，$v$ 为 $\operatorname{sta}(w)$ 即 $w$ 所属等价类对应的状态（由 SAM 的定义可知这个状态一定存在），$\operatorname{link}(u)$ 即为 $v$。特别的，$rt$ 没有 $\operatorname{link}$ 指针；

小结

在开始介绍如何构造 SAM 前，我们先小结一下：

• 原串 $S$ 的每一个子串可以根据 $\operatorname{endpos}$ 来划分为若干个等价类，每个等价类对应一个状态；
• 对于每个状态 $u$，$\operatorname{E}(u)$ 中包含了 $\operatorname{long(u)}$ 长度从 $\operatorname{slen}(u)$ 到 $\operatorname{len}(u)$ 的所有后缀（引理 3）；
• 从状态 $u$ 出发不断跳 $\operatorname{link}$ 到 $rt$ 路径上所有状态的等价类并起来就是 $\operatorname{long}(u)$ 的所有后缀（引理 3 推出）；
• 设 $A=E(u)$ 即状态 $u$ 代表的等价类，$w$ 为 $\operatorname{long}(A)$ 最长的满足 $w\notin A$ 的一个后缀，$v$ 为 $\operatorname{sta}(w)$ 即 $w$ 所属等价类对应的状态（由 SAM 的定义可知这个状态一定存在），则 $\operatorname{link}(u)$ 即为 $v$。特别的，$rt$ 没有 $\operatorname{link}$ 指针。所有 $\operatorname{link}$ 指针构成一棵以 $rt$ 为根的内向树，称之为后缀树（引理 6）；

SAM 的构造

构造 SAM 的算法是一个动态的算法。一开始 SAM 中只存在一个代表空串的状态 $rt$，没有任何转移。通过依次插入原串 $S$ 中的每一个字符来动态维护 SAM。

这里将给出算法流程、解释、时空复杂度分析和 C++ 代码。

算法流程

一开始 SAM 中只存在一个编号为 $0$ 的状态 $rt$。为了方便，我们钦定 $\operatorname{long}(rt)=0$，$\operatorname{link}(rt)=-1$。

现在任务是给 SAM 维护的字符串的末尾新加入一个字符 $c$，流程如下：

1. 设上一次加入字符后整个整个字符串 $S$ 对应的状态为 $lst$，即 $\operatorname{long}(lst)=S$；
2. 创建一个新的状态 $pre$，并且令 $\operatorname{len}(pre)=\operatorname{len}(lst)+1$；
3. 从 $lst$ 开始不断跳 $\operatorname{link}$，如果当前状态 $u$ 没有标记 $c$ 的转移，那么令 $to_{u,c}=pre$；
4. 如果跳到了 $rt$ 并且 $rt$ 也没有标记 $c$ 的转移，那么令 $to_{rt,c}=pre$，$\operatorname{link}(pre)=0$（指向状态 $rt$），转到 8；
5. 否则停止跳 $\operatorname{link}$，并设当前跳到的状态为 $p$，$to_{p,c}$ 为 $q$；
6. 若 $\operatorname{len(q)}=\operatorname{len}(p)+1$，令 $\operatorname{link}(pre)=q$；
7. 否则：
   1. 复制 $q$ 到一个新的状态 $cpy$（只复制 $\operatorname{link}$ 以及 $to_{q,*}$）；
   2. 令 $\operatorname{len}(cpy)=\operatorname{len}(p)+1,\operatorname{link}(pre)=cpy$；
   3. 从 $p$ 开始不断跳 $\operatorname{link}$，设当前跳到的状态为 $u$，则：
      • 若 $u=-1$ 或 $to_{u,c}\not=q$，停止跳 $\operatorname{link}$；
      • 否则令 $to_{u,c}=cpy$；
   4. 令 $\operatorname{link}(q)=cpy$，转到 8；
8. 令 $lst=pre$，插入操作完成；

算法解释

为了表述方便，设 $S1$ 为插入 $c$ 之前的 $S$，$S2$ 为插入 $c$ 之后的 $S$ 即 $S1+c$。

1. 为之后的操作做准备；

2. 插入字符 $c$ 后，$\operatorname{endpos}(S2)=\{|S1|+1\}$ 一定会成为一个新的等价类，所以需要分配新的状态 $pre$ 来代表它。而 $\operatorname{len}(pre)$ 一定是 $|S1|+1$，$lst$ 中最长的字符串显然就是 $S1$，所以令 $\operatorname{len}(pre)=\operatorname{len}(lst)+1$；

3. 考虑新建转移到 $pre$，不断枚举 $S1$ 的后缀，如果还没有标记为 $c$ 的转移就可以新建标记为 $c$ 的转移到 $pre$；

4. 跳到 $rt$ 还没结束代表字符 $c$ 是第一次出现，因为 $rt$ 没有到 $c$ 的转移表明 $S1$ 不存在 $c$ 这个子串，那么 $\operatorname{link}(pre)$ 自然要指向状态 $rt$，因为 $S2$ 不存在非空真后缀；

5. 为之后的操作做准备，注意此时所有到 $pre$ 的转移已处理完成，接下来的所有步骤都是在处理 $\operatorname{link}(pre)$；

6. 若 $E(q)$ 中最长的那个就是 $\operatorname{long}(p)+c$ 即 $S1$ 的某个后缀加上字符 $c$，那么 $\operatorname{long}(q)$ 就一定是 $S2$ 最长的真后缀，所以可以让 $\operatorname{link}(pre)$ 指向 $q$；

7. 否则一定有 $\operatorname{len}(q)>\operatorname{len}(p)$。发现所有 $A=\{s|s\in E(q),|s|\le \operatorname{len}(p)+1\}$ 中的字符串一定是 $S1$ 的某个后缀加上字符 $c$，而 $B=E(q)-A$ 中的一定不是。那么 $A$ 中的字符串的 $\operatorname{endpos}$ 集合一定会加入元素 $|S2|$，$B$ 中的则一定不会，所以 $A$ 和 $B$ 不再属于同一个等价类。

   此时就需要分裂 $q$ 代表的等价类。具体的，创建一个新的状态 $cpy$，把 $q$ 的所有“出边”都复制过去。

   接下来的工作就是让 $cpy$ 表示 $A$，原来的 $q$ 表示 $B$。

   首先 $A$ 中最长的字符串的长度显然是 $\operatorname{len}(p)+1$，那么令 $\operatorname{len}(cpy)=\operatorname{len}(p)+1$，而 $B$ 中最长的字符串没有改变，所以无需对 $\operatorname{len}(q)$ 进行任何操作。

   接下来不难发现 $\operatorname{long}(cpy)$ 一定是 $S2$ 的最长的真后缀，所以令 $\operatorname{link}(pre)$ 指向 $cpy$。

   然后遍历 $p$ 所有的后缀的状态 $u$。因为 $\operatorname{len}(u)\le \operatorname{len}(p)$，所以若 $u$ 有标记 $c$ 的转移到 $q$，那么转移得到的字符串一定属于 $A$，所以让 $to_{u,c}=cpy$；否则 $U=\operatorname{endpos}(s+c|s\in \operatorname{E}(u))$ 一定包含且不等于 $Q=\operatorname{endpos}(s\in E(q))$，那么 $\operatorname{long}(u)$ 的后缀的 $\operatorname{endpos}$ 集合更不可能满足要求，所以可以停止跳 $\operatorname{link}$。

   最后由于 $\operatorname{long}(cpy)$ 一定是 $\operatorname{long}(q)$ 的最长真后缀，所以令 $\operatorname{link}(q)$ 指向 $cpy$；

8. 更新 $lst$，为之后的插入做准备；

复杂度分析

记 $n=|S|$。

• 状态数和转移数

  不难发现，除第一次之外每次插入最多会新建两个状态，所以状态数上限为 $2n-1$。

  而转移会分为两种：

  • $\operatorname{link}$：由于构成内向树，所以上限为 $2n-2$；

  • $to$：

    考虑先随便拎出一棵以 $rt$ 为根的外向生成树，下面来证明非树边数量 $\le n$。

    对于一条非树边 $u\to v$（设 $v=to_{u,c}$），设 $s1$ 为生成树上 $rt$ 到 $u$ 的链构成的字符串，$s2$ 为 $v$ 往后不停走字典序最小的边直到不能走的路径构成的字符串。

    考察字符串 $s1+c+s2$，很显然它是 $S$ 的一个后缀，否则就还能继续走下去。那么这是一个非树边到 $S$ 的后缀的映射。

    而不难发现 $c$ 是 $s1+c+s2$ 对应的路径上第一条非树边，所以这个映射是双向的，即一一对应。

    故非树边条数 $\le |S|=n$；

  那么转移数的上限为 $5n-3$，实际上很难卡满。

• 空间复杂度

由于状态数上限为 $2n-1$，转移数上限为 $3n-2$，所以空间复杂度为 $O(n)$。

特别的，若字符集较小，那么往往采用数组存储 $to$，此时空间复杂度为 $O(nV)$。

若字符集较大，往往采用可持久化线段树来存储 $to$，此时空间复杂度为 $O(n\log V)$。

• 时间复杂度

  较难证明的部分是两个跳 $\operatorname{link}$ 的步骤。不难发现，步骤 3 跳的总次数和转移数相当，所以是 $O(n)$ 的。

  而步骤 7.3 就有点复杂了，注意到有一个引理：

  引理

  对于一个状态 $u$，设 $A=\{(v,c)|to_{v,c}=u\}$ 即其所有入边。

  那么 $\forall (v_i,c_i)\in A$，$c_i$ 相同，$v_i$ 在后缀树上形成一条链（$v_i$ 中的字符串互为后缀）。

  且 $\text{len}(u)=\max\limits_{(v,c)\in A}\{\text{len}(v)+1\},\text{slen}(u)=\min\limits_{(v,c)\in A}\{\text{slen}(v)+1\}$。

  这是显然的，因为一个状态中的字符串一定互为后缀，并且 SAM 包含了原串的所有子串。

  注意到 $cpy$ 的所有入边只会在 7.3 中产生，并且每跳一次 $\text{link}$ 都会使得：

  • $\text{slen}(u)$ 减少；
  • $\text{slen}(cpy)$ 减少；
  • $\text{len}(\text{link}(cpy))$ 减少；

  并且由于 $cpy=\text{link}(pre)$，并且 $pre$ 会成为新的 $lst$，所以 7.3 中每跳一次 $\text{link}$ 都会使得 $\text{len}(\text{link}(\text{link}(lst)))$ 减少。

  考虑一次插入操作最多使 $\text{len}(\text{link}(\text{link}(pre)))$ 增加多少：

  • 若执行了步骤 6，即 $\text{link}(pre)$ 变为 $q$，则 $p$ 最深也是 $\text{link}(lst)$。

    根据引理，$\text{link}(q)$ 的入边 $(v_i,c_i)$ 一定满足 $v_i$ 在 $\text{link}(lst)$ 的 $\text{link}$ 链上，并且 $v_i$ 为 $\text{link}(lst)$ 的祖先，则 $\text{len}(v_i)\le \text{len}(\text{link}(\text{link}(lst)))$，那么 $\text{len}(\text{link}(\text{link}(pre)))\le \text{len}(\text{link}(\text{link}(lst)))+1$；

    

  • 若执行了步骤 7，由于 $\text{link}(pre)=cpy$，$\text{link}(cpy)=\text{link(q)}$，所以重复步骤 6 的证明，$\text{len}(\text{link}(\text{link}(pre)))\le \text{len}(\text{link}(\text{link}(lst)))+1$；

  综上，每次插入操作 $\text{len}(\text{link}(\text{link}(lst)))$ 最多加 $1$，而每次执行 7.3 都会让其减少至少 $1$，那么 7.3 的总执行次数是 $O(n)$ 的。

  所以构建 SAM 的时间复杂度为 $O(nk)$（其中 $k$ 是访问和修改 $to$ 的时间复杂度，若使用数则为 $O(1)$，使用可持久化线段树为 $O(\log V)$）。

const int S=1000005,V=26; // 字符串最大长度，字符集大小

struct SAM
{
	int tot,lst;
	int len[S*2],to[S*2][V],link[S*2]; // 记得开两倍
	inline void init() // 初始化
	{
		for(int i=0;i<=tot;i++)
		{
			len[i]=link[i]=0;
			memset(to[i],0,sizeof(to[i]));
		}
		tot=lst=0;
		link[0]=-1; // 记得让 link(rt)=-1
	}
	inline void ins(int c) // 在末尾插入一个字符
	{
        // 新建状态（第 1、2 步）
		int pre=++tot;
		len[pre]=len[lst]+1;
        // 处理到 pre 的转移（第 3 步）
		int p=lst;
		while(p!=-1&&to[p][c]==0) to[p][c]=pre,p=link[p];
		if(p==-1) link[pre]=0; // 第 4 步
		else
		{
			int q=to[p][c]; // 第 5 步
			if(len[q]==len[p]+1) link[pre]=q; // 无需分裂（第 6 步）
			else // 分裂状态 q（第 7 步）
            {
                // 复制 q 到新状态 cpy，令 link(pre)=cpy（7.1、7.2）
				int cpy=++tot;
				len[cpy]=len[p]+1;
				memcpy(to[cpy],to[q],sizeof(to[q]));
				link[cpy]=link[q];
				link[pre]=cpy;
                // 处理到 cpy 的转移（7.3）
				while(p!=-1&&to[p][c]==q) to[p][c]=cpy,p=link[p];
				link[q]=cpy; // 令 link(q)=cpy（7.4）
			}
		}
		lst=pre; // 第 8 步
	}
};

一些额外信息的求解

值得注意的是，这些信息的求解的时间复杂度均为 $O(n)$。

• 结束标记

  只需要在构建完 SAM 后，从 $lst$ 出发不断跳 $\operatorname{link}$，把经过的状态全都打上标记即可。

• 建立后缀树

  只需要在构建完 SAM 后，对于所有 $1\le u$ 的 $u$，在 $\operatorname{link}(u)$ 的儿子列表中加入 $u$ 即可。

• 两个子串的最长公共后缀

  找到这两个子串所属的状态 $x,y$，它们的最长公共后缀所属的状态 $z$ 即为 $x,y$ 在后缀树上的 $\operatorname{LCA}$。

• $|\operatorname{E}(u)|$（每个节点对应的等价类中的字符串个数）

  由于引理 3，$|\operatorname{E}(u)|$ 即为 $\operatorname{len}(u)-\operatorname{len}(\operatorname{link}(u))$。

• $siz_u=|\operatorname{endpos}(s)|,s\in\operatorname{E}(u)$（每个节点对应的等价类中的字符串出现的次数）

  构建 SAM 时让 $siz_{pre}=1$，注意到这样标记的实际上是 $S$ 的每个前缀，一个子串的出现次数等于它是多少个前缀的后缀，所以构建完成后只需要在后缀树上求一次子树 $siz$ 和即可。

  注意复制节点的时候无需复制 $siz$，因为一个等价类中最长的那个字符串才有可能是 $S$ 的前缀，而这个最长的字符串一定在分裂之后的 $E(q)$ 中。

  代码

  const int S=1000005,V=26;
  
  struct SAM
  {
  	int tot,lst;
  	int len[S*2],to[S*2][V],link[S*2];
  	vector<int> son[S*2]; // 后缀树中每个状态的儿子
  	int siz[S*2]; // 每个状态代表的等价类中每个字符串出现了几次
  	inline void init() // 初始化
  	{
  		for(int i=0;i<=tot;i++)
  		{
  			len[i]=link[i]=siz[i]=0;
  			memset(to[i],0,sizeof(to[i]));
  			son[i].clear();
  		}
  		tot=lst=0;
  		link[0]=-1;
  	}
  	inline void ins(int c) // 在末尾插入一个字符
  	{
  		int pre=++tot;
  		len[pre]=len[lst]+1;
  		siz[pre]=1; // 标记
  		int p=lst;
  		while(p!=-1&&to[p][c]==0) to[p][c]=pre,p=link[p];
  		if(p==-1) link[pre]=0;
  		else
  		{
  			int q=to[p][c];
  			if(len[q]==len[p]+1) link[pre]=q;
  			else
  			{
  				int cpy=++tot;
  				len[cpy]=len[p]+1;
  				memcpy(to[cpy],to[q],sizeof(to[q]));
  				link[cpy]=link[q];
  				link[pre]=cpy;
  				while(p!=-1&&to[p][c]==q) to[p][c]=cpy,p=link[p];
  				link[q]=cpy;
  			}
  		}
  		lst=pre;
  	}
  	inline void build() // 建后缀树
  	{
  		for(int i=1;i<=tot;i++) son[link[i]].push_back(i);
  	}
  	void getsiz(int u=0) // dfs 求子树和
  	{
  		for(int v:son[u])
  		{
  			getsiz(v);
  			siz[u]+=siz[v];
  		}
  	}
  };
  

• $mnr_u=\min\limits_{v\in \operatorname{endpos}(s),s\in\operatorname{E}(u)} v$（每个节点对应的等价类中的字符串的最早出现的右端点）

  和 $siz_u$ 一样，构建时每个前缀的 $mnr$ 就是这个前缀的长度，构建完后在后缀树上求子树 $\min$ 即可。

经典例题

P3804 【模板】后缀自动机 (SAM)

注意到状态 $u$ 下的所有字符串出现次数均为 $siz_u$，显然选最长的最优，那么求出 $siz$ 后对所有 $siz_u>1$ 的 $u$ 的 $len_u\times siz_u$ 取 $\max$ 即可。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

const int S=1000005,V=26;

struct SAM
{
	int tot,lst;
	int len[S*2],to[S*2][V],link[S*2];
	vector<int> son[S*2];
	int siz[S*2];
	inline void init()
	{
		for(int i=0;i<=tot;i++)
		{
			len[i]=link[i]=siz[i]=0;
			memset(to[i],0,sizeof(to[i]));
			son[i].clear();
		}
		tot=lst=0;
		link[0]=-1;
	}
	inline void ins(int c)
	{
		int pre=++tot;
		len[pre]=len[lst]+1;
		siz[pre]=1;
		int p=lst;
		while(p!=-1&&to[p][c]==0) to[p][c]=pre,p=link[p];
		if(p==-1) link[pre]=0;
		else
		{
			int q=to[p][c];
			if(len[q]==len[p]+1) link[pre]=q;
			else
			{
				int cpy=++tot;
				len[cpy]=len[p]+1;
				memcpy(to[cpy],to[q],sizeof(to[q]));
				link[cpy]=link[q];
				link[pre]=cpy;
				while(p!=-1&&to[p][c]==q) to[p][c]=cpy,p=link[p];
				link[q]=cpy;
			}
		}
		lst=pre;
	}
	inline void build()
	{
		for(int i=1;i<=tot;i++) son[link[i]].push_back(i);
	}
	void getsiz(int u=0)
	{
		for(int v:son[u])
		{
			getsiz(v);
			siz[u]+=siz[v];
		}
	}
};

int n;
char a[S];
SAM sam;

int main()
{
	scanf("%s",a+1);
	n=strlen(a+1);
	sam.init();
	for(int i=1;i<=n;i++) sam.ins(a[i]-'a');
	sam.build();
	sam.getsiz();
	long long ans=0;
	for(int i=0;i<=sam.tot;i++) if(sam.siz[i]>1) ans=max(ans,1ll*sam.len[i]*sam.siz[i]);
	printf("%lld\n",ans);
	return 0;
}

P4070 [SDOI2016]生成魔咒

考虑新加入的字符会产生多少个新的非空子串，设加入新字符之前的长度为 $lstlen$，那么只有 $\operatorname{endpos}'(\{lstlen+1\})$ 中的字符串是新的非空子串。

考虑哪个状态代表的等价类是 $\operatorname{endpos}'(\{lstlen+1\})$，显然只有新加入的状态 $pre$ 是。$pre$ 中的字符串个数很好求，即为 $\operatorname{len}(pre)-\operatorname{len}(\operatorname{link}(pre))$。

那么每次让答案累加上 $\operatorname{len}(pre)-\operatorname{len}(\operatorname{link}(pre))$ 即可。

#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

const int S=100005;

struct SAM
{
	int tot,len[S*2],link[S*2];
	map<int,int> to[S*2];
	int lst;
	inline void init()
	{
		for(int i=0;i<=tot;i++) len[i]=link[i]=0,to[i].clear();
		link[0]=-1;
	}
	inline void ins(int c)
	{
		int pre=++tot;
		len[pre]=len[lst]+1;
		int p=lst;
		while(p!=-1&&to[p].find(c)==to[p].end()) to[p][c]=pre,p=link[p];
		if(p==-1) link[pre]=0;
		else
		{
			int q=to[p][c];
			if(len[q]==len[p]+1) link[pre]=q;
			else
			{
				int cpy=++tot;
				len[cpy]=len[p]+1;
				to[cpy]=to[q],link[cpy]=link[q];
				link[pre]=cpy;
				while(p!=-1&&to[p][c]==q) to[p][c]=cpy,p=link[p];
				link[q]=cpy;
			}
		}
		lst=pre;
	}
};

SAM sam;

int main()
{
	int n;
	scanf("%d",&n);
	sam.init();
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		sam.ins(x);
		ans+=sam.len[sam.lst]-sam.len[sam.link[sam.lst]];
		printf("%lld\n",ans);
	}
}

P3975 [TJOI2015]弦论

双倍经验：SP7258 SUBLEX - Lexicographical Substring Search

原串 $S$ 的每个子串都能表示为从 $rt$ 到某个状态的路径，那么在 SAM 的反 DAG 上跑一边 bfs，求出每个状态出发有多少个子串，然后逐位确定即可。

如果 $k=1$ 每个状态的权值就是 $siz_u$，否则就是 $1$。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

const int S=500005,V=26;

struct SAM
{
	int tot;
	int len[S*2],to[S*2][V],link[S*2];
	vector<int> son[S*2];
	int siz[S*2];
	int lst;
	inline void init()
	{
		for(int i=0;i<=tot;i++)
		{
			len[i]=link[i]=siz[i]=0;
			memset(to[i],0,sizeof(to[i]));
			son[i].clear();
		}
		tot=lst=0;
		link[0]=-1;
	}
	inline void ins(int c)
	{
		int pre=++tot;
		len[pre]=len[lst]+1;
		siz[pre]=1;
		int p=lst;
		while(p!=-1&&to[p][c]==0) to[p][c]=pre,p=link[p];
		if(p==-1) link[pre]=0;
		else
		{
			int q=to[p][c];
			if(len[q]==len[p]+1) link[pre]=q;
			else
			{
				int cpy=++tot;
				len[cpy]=len[p]+1;
				memcpy(to[cpy],to[q],sizeof(to[q]));
				link[cpy]=link[q];
				link[pre]=cpy;
				while(p!=-1&&to[p][c]==q) to[p][c]=cpy,p=link[p];
				link[q]=cpy;
			}
		}
		lst=pre;
	}
	inline void build()
	{
		for(int i=1;i<=tot;i++) son[link[i]].push_back(i);
	}
	void getsiz(int u=0)
	{
		for(int v:son[u])
		{
			getsiz(v);
			siz[u]+=siz[v];
		}
	}
};

int n,t;
long long k;
char a[S];
SAM sam;
vector<int> to[S*2];
int ind[S*2];
long long cnt[S*2];

int main()
{
	scanf("%s",a+1);
	n=strlen(a+1);
	scanf("%d%lld",&t,&k);
	sam.init();
	for(int i=1;i<=n;i++) sam.ins(a[i]-'a');
	sam.build();
	sam.getsiz();
	for(int i=0;i<=sam.tot;i++)
	{
		for(int j=0;j<V;j++)
		{
			int v=sam.to[i][j];
			if(v!=0) to[v].push_back(i),ind[i]++;
		}
	}
	queue<int> q;
	for(int i=0;i<=sam.tot;i++)
	{
		cnt[i]=t?sam.siz[i]:1;
		if(ind[i]==0) q.push(i);
	}
	cnt[0]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int v:to[u])
		{
			cnt[v]+=cnt[u];
			if(--ind[v]==0) q.push(v);
		}
	}
	if(k>cnt[0]) return puts("-1"),0;
	int u=0;
	while(k>0)
	{
		for(int i=0;i<V;i++)
		{
			int v=sam.to[u][i];
			if(v==0) continue;
			if(cnt[v]<k) k-=cnt[v];
			else
			{
				k-=t?sam.siz[v]:1;
				printf("%c",'a'+i);
				u=v;
				break;
			}
		}
	}
	printf("\n");
	return 0;
}

P4248 [AHOI2013]差异

建反串的 SAM，在后缀树上 dp 即可。

SP1811 LCS - Longest Common Substring

对于这种多个字符串的问题，通常是要用广义 SAM 来做，但是这里介绍一种“伪广义 SAM”。

考虑把输入的两个字符串 $A$ 和 $B$ 在中间加入一个分隔符 # 后拼接起来加入 SAM，即 $A+\#+B$ 这样。加入的过程中若当前字符属于 $A$ 则给加入后 $S$ 对应的状态打上 $A$ 标记，否则打上 $B$ 标记，最后在后缀树上让每个点的标记都贡献到它的祖先上。

这样一来所有同时被打上 $A$ 和 $B$ 标记的状态中的字符串都是 $A$ 和 $B$ 的公共子串，那么统计这些状态的 $\operatorname{len}$ 的最大值即可。

SP1812 LCS2 - Longest Common Substring II 这题也类似，不过要注意分隔符要两两不同，要不然带分隔符的子串可能也会被打上标记。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int S=500005,V=27;

struct SAM
{
	int tot;
	int len[S*2],to[S*2][V],link[S*2];
	vector<int> son[S*2];
	bool app[2][S*2];
	int lst;
	inline void init()
	{
		for(int i=0;i<=tot;i++)
		{
			len[i]=link[i]=0;
			memset(to[i],0,sizeof(to[i]));
			app[0][i]=app[1][i]=false;
			son[i].clear();
		}
		tot=lst=0;
		link[0]=-1;
	}
	inline void ins(int c,int tpe)
	{
		int pre=++tot;
		len[pre]=len[lst]+1;
		app[tpe][pre]=true;
		int p=lst;
		while(p!=-1&&to[p][c]==0) to[p][c]=pre,p=link[p];
		if(p==-1) link[pre]=0;
		else
		{
			int q=to[p][c];
			if(len[q]==len[p]+1) link[pre]=q;
			else
			{
				int cpy=++tot;
				len[cpy]=len[p]+1;
				memcpy(to[cpy],to[q],sizeof(to[q]));
				link[cpy]=link[q];
				link[pre]=cpy;
				while(p!=-1&&to[p][c]==q) to[p][c]=cpy,p=link[p];
				link[q]=cpy;
			}
		}
		lst=pre;
	}
	inline void build()
	{
		for(int i=1;i<=tot;i++) son[link[i]].push_back(i);
	}
	inline void calctag(int u=0)
	{
		for(int v:son[u])
		{
			calctag(v);
			for(int i=0;i<=1;i++) app[i][u]|=app[i][v];
		}
	}
};

int n,m;
char a[S],b[S];
SAM sam;

int main()
{
	scanf("%s%s",a+1,b+1);
	n=strlen(a+1),m=strlen(b+1);
	sam.init();
	for(int i=1;i<=n;i++) sam.ins(a[i]-'a',0);
	sam.ins(26,1);
	for(int i=1;i<=m;i++) sam.ins(b[i]-'a',1);
	sam.build();
	sam.calctag();
	int ans=0;
	for(int i=0;i<=sam.tot;i++) if(sam.app[0][i]&&sam.app[1][i]) ans=max(ans,sam.len[i]);
	printf("%d\n",ans);
	return 0;
}

P3649 [APIO2014] 回文串

有两种做法。

• Manacher + SAM

  前置知识：Manacher。

  由于 $S$ 的本质不同回文子串个数上限是 $|S|$，所以可以建出 SAM 之后跑 Manacher 找到每个本质不同回文子串 $S_{[l_i,r_i]}$，再从 $S_{[1,r_i]}$ 这个前缀对应的状态开始倍增跳 $\operatorname{link}$ 找到 $S_{[l_i,r_i]}$ 对应的等价类并统计答案。

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

• SAM

  建 SAM 时维护每个状态中的字符串的最后出现位置 $mx_u$，建完 SAM 后在 SAM 上跑反串 $S'$ 和 $S$ 的所有子串的匹配。假设跑到 $S'_{[1,n-l+1]}$ 时匹配到了状态 $u$，匹配长度为 $len$。那么若 $mx_u\in[l,l+len-1]$：

  

  此时绿色部分 $S_{[l,mx_u]}$ 一定是回文串，并且它的出现次数一定是 $siz_u$ 即状态 $u$ 中的每个字符串出现的次数。

  只统计 $S_{[l,mx_u]}$ 是不够全面的，还需要不断跳 $u$ 的 $\operatorname{link}$ 直到 $mx_u\notin [l,l+len-1]$ 或 $\operatorname{len}(u)< mx_u-l+1$，因为这些状态中的字符串 $S_{[l,mx_u]}$ 也是回文串。

  注意到 $mx$ 一样的 $u$ 只有 $\operatorname{len}(u)$ 最小的才会有贡献，所以可以用倍增跳 $\operatorname{link}$。

  不难发现一个子串只会被统计一次，所以时间复杂度即为 $O(n\log n)$。

  另外似乎还有一种做法即跳 $\operatorname{link}$ 时给跳过的状态打上标记，下一次不跳。这种做法时间复杂度是 $O(n)$ 的，但是正确性不是很显然。

虽然第二种做法很难写，但是可以增加对 SAM 的理解。所以我写了第二种做法，然后 BZOJ 过了洛谷一直 MLE……

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <map>

using namespace std;

const int S=300001,V=26,BS=20;

struct SAM
{
	int tot;
	int len[S*2],link[S*2];
	map<char,int> to[S*2];
	vector<int> son[S*2];
	int siz[S*2],mx[S*2];
	vector<int> fa[S*2];
	int lst;
	inline void init()
	{
		for(int i=0;i<=tot;i++)
		{
			len[i]=link[i]=siz[i]=mx[i]=0;
			to[i].clear();
			son[i].clear();
			fa[i].clear();
		}
		link[0]=-1;
		tot=lst=0;
	}
	inline void ins(int c,int pp)
	{
		int pre=++tot;
		len[pre]=len[lst]+1;
		siz[pre]=1,mx[pre]=pp;
		int p=lst;
		while(p!=-1&&to[p][c]==0) to[p][c]=pre,p=link[p];
		if(p==-1) link[pre]=0;
		else
		{
			int q=to[p][c];
			if(len[q]==len[p]+1) link[pre]=q;
			else
			{
				int cpy=++tot;
				len[cpy]=len[p]+1;
				to[cpy]=to[q];
				link[cpy]=link[q];
				link[pre]=cpy;
				while(p!=-1&&to[p][c]==q) to[p][c]=cpy,p=link[p];
				link[q]=cpy;
			}
		}
		lst=pre;
	}
	inline void build()
	{
		for(int i=1;i<=tot;i++) son[link[i]].push_back(i);
	}
	void dfs(int u=0)
	{
		if(u!=0)
		{
			fa[u].push_back(link[u]);
			for(int i=1;i<=BS;i++)
			{
				if(fa[u][i-1]==-1) break;
				else
				{
					int fat=fa[u][i-1];
					if(fa[fat].size()<=i-1) break;
					else fa[u][i]=fa[fat][i-1];
				}
			}
		}
		for(int v:son[u])
		{
			dfs(v);
			siz[u]+=siz[v],mx[u]=max(mx[u],mx[v]);
		}
		vector<int>().swap(son[u]); // 释放 vector 空间
	}
};

int n;
char a[S];
SAM sam;

int main()
{
	scanf("%s",a);
	n=strlen(a);
	sam.init();
	for(int i=0;i<n;i++) sam.ins(a[i]-'a',i);
	sam.build();
	sam.dfs();
	int u=0,len=0;
	long long ans=0;
	for(int i=n-1;i>=0;i--)
	{
		while(u!=-1&&sam.to[u][a[i]-'a']==0)
		{
			u=sam.link[u];
			if(u!=-1) len=sam.len[u];
		}
		if(u==-1) u=0,len=0;
		else u=sam.to[u][a[i]-'a'],len++;
		int r=i+len-1,v=u;
		while(sam.mx[v]<=r&&sam.len[v]>=sam.mx[v]-i+1)
		{
			for(int j=BS;j>=0;j--)
			{
				if(sam.fa[v].size()>j&&sam.mx[sam.fa[v][j]]==sam.mx[v]&&sam.len[sam.fa[v][j]]>=sam.mx[v]-i+1) v=sam.fa[v][j];
			}
			if(sam.mx[v]>=i) ans=max(ans,1ll*(sam.mx[v]-i+1)*sam.siz[v]);
			if(sam.fa[v].size()>0) v=sam.fa[v][0];
			else break;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

P5685 [JSOI2013]快乐的 JYY

双倍经验：P5555 秩序魔咒

和上一题差不多，建完“伪广义” SAM 之后跑 manacher+哈希求出 $A$ 的所有本质不同的回文子串 $[l,r]$，然后找到 $A_{[1,r]}$ 即前缀 $r$ 对应的 SAM 上的状态，倍增找到 $A_{[l,r]}$ 所在的状态，然后统计答案即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>

using namespace std;

const int S=100005,V=27,BS=25,bse=31,p1=998244353,p2=1000000007;

struct SAM
{
	int tot;
	int len[S*4],to[S*4][V],link[S*4];
	vector<int> suf,son[S*4];
	int siz[2][S*4];
	int fa[S*4][BS+1];
	int lst;
	inline void init()
	{
		for(int i=0;i<=tot;i++)
		{
			len[i]=link[i]=siz[0][i]=siz[1][i]=0;
			memset(to[i],0,sizeof(to[i]));
			vector<int>().swap(son[i]);
		}
		vector<int>().swap(suf);
		tot=lst=0;
		link[0]=-1;
		suf.push_back(0);
	}
	inline void ins(int c,int tpe)
	{
		int pre=++tot;
		len[pre]=len[lst]+1;
		suf.push_back(pre);
		siz[tpe][pre]=1;
		int p=lst;
		while(p!=-1&&to[p][c]==0) to[p][c]=pre,p=link[p];
		if(p==-1) link[pre]=0;
		else
		{
			int q=to[p][c];
			if(len[q]==len[p]+1) link[pre]=q;
			else
			{
				int cpy=++tot;
				len[cpy]=len[p]+1;
				memcpy(to[cpy],to[q],sizeof(to[q]));
				link[cpy]=link[q];
				link[pre]=cpy;
				while(p!=-1&&to[p][c]==q) to[p][c]=cpy,p=link[p];
				link[q]=cpy;
			}
		}
		lst=pre;
	}
	inline void build()
	{
		for(int i=1;i<=tot;i++) son[link[i]].push_back(i);
	}
	void calctag(int u=0)
	{
		fa[u][0]=link[u];
		for(int i=1;i<=BS;i++)
		{
			int tp=fa[u][i-1];
			if(tp==-1) fa[u][i]=-1;
			else fa[u][i]=fa[tp][i-1];
		}
		for(int v:son[u])
		{
			calctag(v);
			for(int j=0;j<=1;j++) siz[j][u]+=siz[j][v];
		}
	}
};

int n,m;
char a[S],b[S];
SAM sam;
char str[S*2];
int ext[S*2];
int pw1[S],pw2[S];
int s1[S],s2[S];
set<pair<int,int>> st;

inline pair<int,int> calchash(int l,int r)
{
	return make_pair(
	(s1[r]-1ll*s1[l-1]*pw1[r-l+1]%p1+p1)%p1,
	(s2[r]-1ll*s2[l-1]*pw2[r-l+1]%p2+p2)%p2);
}

int main()
{
	scanf("%s%s",a+1,b+1);
	sam.init();
	n=strlen(a+1),m=strlen(b+1);
	for(int i=1;i<=n;i++) sam.ins(a[i]-'A',0);
	sam.ins(26,1);
	for(int i=1;i<=m;i++) sam.ins(b[i]-'A',1);
	sam.build();
	sam.calctag();
	pw1[0]=1,pw2[0]=1;
	for(int i=1;i<=n;i++)
	{
		pw1[i]=1ll*pw1[i-1]*bse%p1;
		pw2[i]=1ll*pw2[i-1]*bse%p2;
		s1[i]=(1ll*s1[i-1]*bse%p1+a[i]-'A'+1)%p1;
		s2[i]=(1ll*s2[i-1]*bse%p2+a[i]-'A'+1)%p2;
	}
	for(int i=1;i<=n;i++) str[i*2]=a[i];
	n=n*2+1;
	for(int i=1;i<=n;i+=2) str[i]='#';
	str[0]='@',str[n+1]='$';
	long long ans=0;
	for(int i=1,pos=0;i<=n;i++)
	{
		if(pos+ext[pos]>i) ext[i]=min(pos+ext[pos]-i,ext[pos-(i-pos)]);
		while(str[i-ext[i]]==str[i+ext[i]])
		{
			ext[i]++;
			if(str[i-ext[i]+1]=='#'&&ext[i]>1)
			{
				int len=ext[i]-1;
				int rb=i/2+len/2;
				pair<int,int> pir=calchash(rb-len+1,rb);
				if(st.count(pir)==0)
				{
					st.insert(pir);
					int u=sam.suf[rb];
					if(sam.len[sam.link[u]]+1>len)
					{
						for(int j=BS;j>=0;j--)
						{
							int to=sam.fa[u][j];
							if(to!=-1&&sam.link[to]!=-1&&sam.len[sam.link[to]]+1>len) u=to;
						}
						u=sam.fa[u][0];
					}
					ans+=1ll*sam.siz[0][u]*sam.siz[1][u];
//					for(int j=rb-len+1;j<=rb;j++) printf("%c",a[j]);
//					printf(" : %d * %d\n",sam.siz[0][u],sam.siz[1][u]);
				}
			}
		}
		if(i+ext[i]>pos+ext[pos]) pos=i;
		
	}
	printf("%lld\n",ans);
	return 0;
}