后缀自动机（SAM）学习笔记
算法引入
约定下标从 $1$ 开始，记 $s$ 以 $l$ 开头以 $r$ 结尾的子串为 $s[l:r]$。
约定大写 $S$ 表示自动机状态集合，$S_0$ 表示初始状态，$\delta(x,c)$ 表示从状态 $x$ 走字符 $c$ 的转移边。
在阅读本文前，请确保你已经了解字符串基础概念（至少你要知道自动机是什么吧），可以阅读我的这篇博客。
我曾经说过一句话：
字符串算法就是一堆看起来没什么卵用实际上很有用的算法。
后缀自动机（Suffix Automaton，简称 SAM）虽然目的明确，但是据高二学长 wqs 所说，他做 SAM 题从来没用过它原本的目的。
SAM 被创造出来的目的是一个能接受指定 $S$ 字符串所有后缀的自动机，这样就能 $O(|t|)$ 地判断 $t$ 是不是 $s$ 的后缀了。
考虑 KMP 是能接受以一个完整字符串 $s$ 为后缀的所有字符串 $t$ 的自动机，而由于自动机数学模型每次只能读一个字符，故所有 $s$ 的前缀 $s'$ 对应的状态均在自动机状态集合 $S$ 中。
而类比过来，SAM 的定义是能接受 指定字符串 $s$ 的所有后缀的自动机，那么显然，这个自动机必须保存 $s$ 的所有子串。所以 SAM 可以用来高效地处理子串信息。
直观上，字符串的 SAM 可以理解为给定字符串的所有子串的压缩形式。值得注意的事实是，SAM 将所有的这些信息以高度压缩的形式储存。对于一个长度为 $n$ 的字符串，它的空间复杂度仅为 $O(n)$。此外，构造 SAM 的时间复杂度也仅为 $O(n)$。更准确地说，一个 SAM 最多有 $2n-1$ 个节点和 $3n-4$ 条转移边。
算法简述
定义
字符串 $s$ 的 SAM 的定义是一个接受 $s$ 所有后缀的最小的 DFA（确定有限状态自动机）。
应具有的性质
刚刚提到了，SAM 应保存 $s$ 的所有子串信息，即任意子串信息都能从初始状态 $S_0$ 经过若干条转移边得到。由于 SAM 是极小的，那么任意一条从 $S_0$ 出发的路径都应该是 $s$ 的一个子串。故 $s$ 的子串与自动机上从 $S_0$ 出发的路径应具有双射关系。为方便叙述，本文中称一条路径对应一个子串。
由于自动机一次只能读一个字符，所以 $s[1:k]$ 的某个后缀必须通过 $s[1:k-1]$ 的某个后缀加上字符 $s_k$ 转移过来。故为了构建 $s[1:k]$ 的自动机，我们必须先构建 $s[1:k-1]$ 的自动机。换句话说，SAM 的构建应是一个在线的过程，对于任意一个时刻 $i$，自动机都应是可以使用的。所以我们考虑构建方法时可以直接从“如何在一个已经建好的 SAM 后面插入一个字符”的方面考虑。
如何构建
在本段中，请先不管代码实现以及复杂度问题。
为方便叙述，称一个子串的出现位置为它最后一个字符的位置，比如 $s[3:5]$ 的出现位置就是 $5$。
注意到对于多个本质相同的子串，由于我们读入字符串 $t$ 时只考虑它是不是 $s$ 的子串，而不考虑它的位置。所以本质相同的子串显然可以合并为同一个状态。而转移就是这些子串所有结束位置 $e$ 的下一个字符 $s_{e+1}$。考虑令 $\mathrm{endpos_{\mathit{a}}}$ 表示子串 $a$ 的所有结束位置构成的集合。
而容易发现，对于两个子串 $a,b$（钦定 $|a|\ge |b|$），若 $b$ 不是 $a$ 的后缀，那么 $\mathrm{endpos_{\mathit{b}}}\cap \mathrm{endpos_{\mathit{a}}}=\varnothing$，因为任意出现 $b$ 的位置都无法通过向前拓展的方式得到 $a$。而若 $b$ 是 $a$ 的后缀，那么有 $\mathrm{endpos_{\mathit{a}}}\subseteq \mathrm{endpos_{\mathit{b}}}$，因为任意出现了 $a$ 的位置都能通过删掉开头若干个字符得到 $b$，并且显然 $b$ 还可能在其他地方出现。那么显然，对于两个字符串 $a,b(|a|\ge|b|)$，它们 $\mathrm{endpos}$ 的交不是空集就是 $\mathrm{endpos_{\mathit{b}}}$
然后着重考虑多个 $\mathrm{endpos}$ 相同的情况。容易想到若 $\mathrm{endpos}$ 那么对应的转移也相同，或许可以合并为同一个状态，考虑寻找性质。令 $t_1,t_2,\dots t_k$ 为某个满足 $\mathrm{endpos_{\mathit{t_1}}}=\mathrm{endpos_{\mathit{t_2}}}=\cdots=\mathrm{endpos_{\mathit{t_k}}}$ 的极大字符串集合（“极大”是指不存在其它字符串 $\mathrm{endpos}$ 和它们相同），且钦定 $|t_1|\ge |t_2|\ge\dots\ge |t_k|$。首先注意到两长度相同的本质不同子串 $\mathrm{endpos}$ 显然不可能相同，故上面对 $t$ 排列的要求就可以不取等了。由于它们的交不为空，那么所有 $t_i$ 必定都是 $t_1$ 的后缀，不妨从 $t_1$ 每次删掉开头字符考虑，容易发现每删掉一个字符，$\mathrm{endpos}$ 内部的元素是单调变多的，也就是说随着删开头字符，不可能出现 $\mathrm{endpos}$ 从等于 $\mathrm{endpos_{\mathit{t_1}}}$ 变成不等于 $\mathrm{endpos_{\mathit{t_1}}}$ 又变回 $\mathrm{endpos_{\mathit{t_1}}}$ 的情况。换句话说，$\forall i\in[1,k),t_{i+1}$ 必定是由 $t_i$ 删掉开头字符得到的。
考虑把这些 $t_i$ 视为同一个等价类 $x$，那么根据之前的猜想，可以把一个等价类作为一个状态（下文的所有 $x$ 以及带任意下标的 $x$ 若没有另行说明均指代某自动机状态或其代表的等价类）。如果删掉 $t_k$ 的开头字符得到 $t'$，它必定属于另一个等价类，记为 $\mathrm{link_{\mathit{x}}}$。容易发现 $x\to \mathrm{link_{\mathit{x}}}$ 的关系形成了一个以初始状态 $S_0$ 为根的树形结构。其中对于任意一条树边，有 $\mathrm{endpos_{\mathit{x}}}\subsetneq \mathrm{endpos_{link_{\mathit{x}}}}$，对于任意一个 $x$，它的所有儿子对应的 $\mathrm{endpos}$ 必定互不相交（因为如果两 $\mathrm{endpos}$ 相交，那么它们对应的状态必定是祖先和后代的关系）。
对于一个等价类 $x$，它必定有一个最长的字符串 $\mathrm{longest_{\mathit{x}}}$，它的长度记作 $\mathrm{len_{\mathit{x}}}$。以及最短的字符串 $\mathrm{shortest_{\mathit{x}}}$，它的长度记作 $\mathrm{minlen_{\mathit{x}}}$。只要找到了这两个字符串就能确定等价类 $x$ 内所有字符串。注意到 $\mathrm{len_{link_{\mathit{x}}}}+1=\mathrm{minlen_{\mathit{x}}}$（除非 $x=S_0$），所以我们其实不需要维护 $\mathrm{minlen_{\mathit{x}}}$ 和 $\mathrm{shortest_{\mathit{x}}}$。在后文我会说明其实 $\mathrm{longest_{\mathit{x}}}$ 也不需要维护。此外，容易发现从任意结点 $x$ 每次跳 $\mathrm{link_{\mathit{x}}}$ 直到 $S_0$，路径上所有等价类内字符串恰好是从 $\mathrm{longest_{\mathit{x}}}$ 开始每次删掉开头字符直到变为空串的所有字符串。
根据前文的猜想，考虑已经构建好了 $s[1:k-1]$ 的 SAM，如何插入 $s_k$，令 $c=s_k$。
首先显然地，子串 $s[1:k]$ 此时必定只出现了一次。那么新建一个结点 $x$ 包含所有第一次出现 的字符串，显然它们必然都是 $s[1:k]$ 的后缀，那么设 $x_0$ 为 $s[1:k-1]$ 所在的自动机状态。那么有 $\mathrm{len_{\mathit{x}}}=\mathrm{len_{\mathit{x_0}}}+1$ 显然所有有可能存在转移边 $\delta(x',c)=x$ 的 $x'$ 必定是 $x_0$ 的祖先（包括它自己）。
考虑从 $x_0$ 开始一步一步往上跳 $\mathrm{link}$，最下面的一些状态本来就不存在转移边 $\delta(x',c)$，可以直接令 $\delta(x',c)=x$。考虑找到第一个存在 $\delta(x',c)$ 的 $x'$，记这个 $x'$ 为 $p$，又记 $\delta(p,c)=q$（注意可能找不到这个 $x'$，即 $\delta(S_0,c)$ 不存在，但是如果 $x'=S_0$ 也要进行下一步）。接下来分两种情况：
- $\mathrm{len_{\mathit{q}}}=\mathrm{len_{\mathit{p}}}+1$
说明 $q$ 内所有字符串均能通过 $p$ 及其祖先内的字符串加上字符 $c$ 得到，即它们全都是子串 $s[1:k]$ 的后缀，由于 $p$ 是 $x_0$ 的祖先中最深的拥有 $\delta(p,c)$ 转移边的结点，也就是说 $\mathrm{longest_{\mathit{q}}}$ 是从 $s[1:k]$ 开始依次删除开头字符能得到的第一个 $\mathrm{endpos}$ 与 $x$ 不同的字符串，即 $q=\mathrm{link_{\mathit{x}}}$。
- $\mathrm{len_{\mathit{q}}}\ne \mathrm{len_{\mathit{p}}}+1$。
此时 $q$ 只有一部分（更具体地说，是长度小于 $len_p+1$ 的那一部分）能通过 $p$ 及其祖先内的字符串加上字符 $c$ 得到，考虑把这一部分分裂出来，得到一个新状态 $q'$，然后剩下的字符串视作 $q''$。
考虑 $q',q''$ 的信息（$\mathrm{len},\mathrm{link},\delta$）应该怎么赋。
首先对于 $\delta$，由于 $q$ 的转移边 $q'$ 和 $q''$ 显然都能转移（在对应位置都出现过），所以直接复制即可。
然后是 $\mathrm{link}$，显然 $\mathrm{link_{\mathit{x}}}=\mathrm{link_{\mathit{q''}}}=q',\mathrm{link_{\mathit{q'}}}=\mathrm{link_{\mathit{q}}}$。
接下来是 $\mathrm{len}$，根据定义可得 $\mathrm{len_{\mathit{q'}}}=len_{p}+1,\mathrm{len_{\mathit{q''}}}=\mathrm{len_{\mathit{q}}}$。
然后从 $p$ 往上的一段链本来转移到 $q$，由于从 $p$ 分裂开，故这些 $\delta'(p',c)$ 一直到某位置的 $\delta(p',c)$ 是 $q$ 的祖先为止都要重新赋值为 $q'$。
具体实现的时候，可以只新建一个 $q'$，然后 $q''$ 直接从 $q$ 上修改得到。
然后比如你可能要维护 $\mathrm{endpos}$ 的各种信息。在离线的情况下，假如你只维护 $\mathrm{endpos}$ 的大小那比较简单，每次新建的结点 $x$ 大小是 $1$（加上子树信息，它可能在后面得到儿子），其余结点就是一个子树和（考虑等价类的性质）。如果要维护 $\mathrm{endpos}$ 内的元素，需要用一个叫“线段树的可持久化合并”的东西，具体过程大概就是在线段树合并时新建一个版本。如果强制在线，可能需要用 LCT 维护（虽然我不知道 LCT 是什么），因为所有点的 $\mathrm{link}$ 随时都会改变。
复杂度证明
前文说过 SAM 的状态数和转移数都是 $O(n)$ 的，并且点数上界是 $2n-1$，边数是 $3n-4$。
首先点数很好证，初始只有一个结点 $S_0$，每一次插入字符至多增加两个结点（$x,q'$），但是前两次显然不可能分裂出 $q'$。能卡到这个上界的字符串必定形如 abbbbb...，因为第三次及以后每次都会分裂出一个 $q'$。
然后是边数。容易发现对于任意一个状态 $q$，都存在一个转移 $(p,q)$ 使得 $\mathrm{len_{\mathit{q}}}=\mathrm{len_{\mathit{p}}}+1$。我们称这样的转移是连续的。
容易发现连续的边必定能组成一棵以 $S_0$ 为根的外向树，故这一部分边数上界是 $2n-2$。考虑非连续转移的数量。
注意到对于一个非连续转移 $u\to v$，必定存在唯一的一条只走连续转移从 $S_0$ 到 $u$ 的路径。然后从 $v$ 开始，走到以 $S_0\to v$ 路径对应的子串开头的后缀中最长的一个所对应的接收状态。容易发现 $u\to v$ 是这一个后缀中第一条非连续转移边。我们可以由此建立一个映射关系 $f(e)$，表示以 $e$ 为第一条非连续转移边对应的后缀。容易发现若 $f(a)=f(b)$，那么必然有 $a=b$（因为一个后缀在自动机上最多只存在一条第一条转移边）。这说明非连续转移边数量小于等于后缀数量。并且容易发现，对于 $s[1:n]$ 后缀，它对应的路径中间显然不可能有非连续转移边（$s[1:n]$ 每次走的路径就是每次插入的 $x_0\to x$），故我们能得到转移数上界为 $3n-3$。但是由于状态数上界 $2n-1$ 只会在形如 abbb... 的字符串中产生，但此时边界数小于 $3n-3$。故我们能得到转移数的上界是 $3n-4$，字符串 abbb...bbbc 就能卡到这个上界，需要注意不一定能卡到上界的字符串都形如这样。
接下来思考构建过程中的时间复杂度。
首先对于暴力从 $x_0$ 向上跳找到 $p$，由于每跳一次就会新增一条转移边，所以这一部分总复杂度就是 $O(n)$ 的。
然后下一步若不分裂 $q$ 复杂度显然是 $O(1)$ 的。若要分裂 $q$，$\mathrm{len},\mathrm{link}$ 的更新都是 $O(1)$ 的，$\delta$ 的更新确实没办法，是 $O(|\Sigma|)$ 的（但是如果你用 map 存边就是 $O(\log |\Sigma|)$ 的，因为你每次操作都会新增一个转移，均摊是插入次数 $O(1)$ 的，但是你插入一条边是 $O(\log |\Sigma|)$ 的）。最后考虑本来指向 $q$ 的转移边更新为 $q'$ 的复杂度。
仍沿用之前实现过程中的变量名。
首先 $p$ 必定是 $\mathrm{link_{\mathit{x_{\mathrm{0}}}}}$ 或其祖先，然后一直到某个 $p'$ 使得 $\delta(p',c)\ne q$ 为止的一段都需要赋值。这个 $p'$ 必然是 $\mathrm{link_{link_{\mathit{x_{\mathrm{0}}}}}}$ 或其祖先，并且它会转移到 $\mathrm{link_{link_{\mathit{x}}}}$，即 $\mathrm{len_{link_{link_{\mathit{x}}}}}=\mathrm{len_{\mathit{p'}}}+1$。那么每跳一次都会使 $\mathrm{len_{\mathit{p'}}}$ 至少减少 $1$，而转移到的 $\mathrm{link_{link_{\mathit{x}}}}$ 就会成为下一次“可能的最大的 $p'$”，那么假如你取一个指针维护这个东西，他就至多会变化 $O(n)$ 次（虽然一般不这么写）。
模板题参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e6+5,inf=0x3f3f3f3f;
i64 n,ans;
char str[N];
vector<int> e[N<<1];
int lnk[N<<1],len[N<<1],endpossz[N<<1],tr[N<<1][26];
int lst,cntn;
void dfs(int x){
for(auto i:e[x]){
dfs(i);
endpossz[x]+=endpossz[i];
}
if(endpossz[x]>1) ans=max(ans,1ll*len[x]*endpossz[x]);
}
void Work(){
lnk[0]=-1;// (1)!
forup(i,1,n){
int x=++cntn,c=str[i]-'a';
len[x]=len[lst]+1;endpossz[x]=1;
int p=lst;
lst=x;
while(~p&&!tr[p][c]){
tr[p][c]=x;
p=lnk[p];
}
if(p==-1){
lnk[x]=0;
continue;
}
int q=tr[p][c];
if(len[q]==len[p]+1){
lnk[x]=q;
}else{
int _q=++cntn;
len[_q]=len[p]+1;endpossz[_q]=0;
lnk[_q]=lnk[q];lnk[q]=lnk[x]=_q;
forup(i,0,25){
tr[_q][i]=tr[q][i];
}
while(~p&&tr[p][c]==q){
tr[p][c]=_q;
p=lnk[p];
}
}
}
forup(i,1,cntn){
e[lnk[i]].push_back(i);
}
dfs(0);
}
signed main(){
scanf(" %s",str+1);
n=strlen(str+1);
Work();
printf("%lld\n",ans);
}
- 把 $\mathrm{link_{0}}$ 设为 $-1$，此处 $-1$ 相当于 $\mathrm{null}$ 状态，即一个不能到达任何接收状态的状态。这样实现起来也更方便。
其它性质
然后在彻底理解 SAM 的正确性后，我们还能发现一些新的性质。
显然 $\mathrm{link}$ 关系会形成一棵树，我们称之为 parent tree。
SAM 肯定是一个 DAG。因为任意一个转移 $(p,q)$，都有 $\mathrm{len_{\mathit{q}}}\le \mathrm{len_{\mathit{p}}}+1$，显然不会形成环。并且这个 DAG 的总路径数小到令人发指，是 $O(n^2)$ 级别（原串中本质不同子串个数）的（随机 DAG 路径数是指数级别的）。因为任意一个是原串子串的字符串都有唯一一条路径与它对应，而对于任意一条不是原串子串的字符串，都必定不存在一条对应的路径。
并且，同一个等价类内部不可能出现“存在两字符串 $s,t$，使得 $s$ 在 $t$ 中能匹配两次”的情况。因为等价类的意义是 $\mathrm{endpos}$ 相同，如果 $s$ 能匹配两次 $t$ 那么必然 $t$ 在前面一次也出现了，这就无限递归了。
常见用法
考虑直接报菜名（排序不分先后，但是大致是按难度排的）。
- 先给定文本串，再给定模式串的多模式匹配
建出文本串 $s$ 的 SAM 后读入模式串 $t_i$ 即可，如果能完整读入说明匹配。复杂度 $O(|s|+\sum |t_i|)$。
- 本质不同子串个数
经典 $O(n\log n)$ SA 例题，但是 SAM 可以做到 $O(n)$，还能求出每个前缀的答案。
本质不同子串个数就是每个等价类的 $\mathrm{len}-\mathrm{minlen}+1=\mathrm{len}-\mathrm{len_{link}}$，每次插入的时候动态维护即可，另外显然分裂 $q$ 的时候不会增加本质不同子串个数。
- 所有本质不同子串总长度
我觉得看了上一个这一个你也能会，等差数列求和即可。
- 出现次数
就是 $\mathrm{endpos}$ 的大小，parent tree 上的子树和。
具体来说，每次新增的 $x$ 自带一个 $\mathrm{endpos}$，其余均为 $0$，然后做子树和。
- 第一次出现位置
和上一个一样，换成求最小值。
- 最小循环移位
容易发现字符串 $S+S$ 包含字符串 $S$ 的所有循环移位作为子串。
所以问题简化为在 $S+S$ 对应的后缀自动机上寻找最小的长度为 $|S|$ 的路径，这可以通过平凡的方法做到：我们从初始状态开始，贪心地访问最小的字符即可。
总的时间复杂度为 $O(|S|)$。
- 所有出现位置
线段树的可持久化合并（这个名字我看一次笑一次）。
用动态开点线段树维护 $\mathrm{endpos}$，然后每个点往父亲合并就是线段树合并。
但是我们在合并的同时可能还要保留儿子的信息，怎么办呢？容易想到可持久化。
具体来说，在线段树合并的基础上，每次新增一个结点。
感觉很抽象啊，建议看代码：
参考代码
然后你就对每个点得到了一棵保存所有 $\mathrm{endpos}$ 的线段树。
复杂度 $O(n\log n)$。
- 两个字符串的最长公共子串
考虑对 $s$ 建 SAM，然后读入 $t$。
如果不能拓展，就暴力跳 $\mathrm{link}$ 知道有对应转移（或者到 $\mathrm{null}$）为止，相当于删掉开头。
显然跳的次数不会超过 $O(|t|)$。
注意转移不一定是连续的，一个比较方便的做法是求出 $t$ 每个右端点是和 $s$ 的公共子串的最小左端点。
复杂度 $O(|s|+|t|)$。
- 多个字符串的最长公共子串
这玩意貌似不算常见。
考虑把所以字符串连在一起，在其间加上互不相同的没在原字符集中出现过的字符。
$$T=C_1+S_1+C_2+S_2\dots +C_k+S_k$$
然后对 $T$ 建 SAM。
容易发现若某子串 $s$ 在 $S_i$ 中出现当且仅当存在一条从以 $C_i$ 结尾的状态，且不经过以其余 $C$ 结尾的状态，能到达 $s$ 所在等价类的路径。
那么 DAG 上 DP，状压统计可达性即可。
这种题 $k$ 不会太大。
- 区间本质不同子串
代码比较毒瘤，但思路其实还算好，参考这篇博客