后缀自动机原理及实现
概述
后缀自动机（Suffix Automaton，简称SAM）是一种用于字符串处理的有限状态自动机（DFA），它可以接受其母串的任何一个后缀，且构造算法为线性算法。下面对其原理及实现进行介绍。
本文中所有SAM示意图皆为SAM Builder生成的图片，构造法处略图来自Menci博客。本文部分内容有摘录参考资料或摘录并改编的部分，参考资料均已附链接。
结构
如图为串abc的SAM示意图，其中，实线黑色箭头表示节点的转移边，虚线蓝色箭头表示后缀链接。
有向无环单词图（Directed Acyclic Word Graph，简称DAWG）
DAWG是SAM的一部分，对于一个DAWG，每个节点（除起始节点外）都可以代表一个或多个子串（的结束点），每条转移边上都有一个字符，从起始节点沿转移边走，每条路径都对应一个子串，即路径上所有边的字符相连构成的。
SAM是一个DFA，它可以接受一些字符串，可以接受的字符串是指从起始节点开始，沿着每一个字符对应的转移边在DAWG上转移，最后到达某个节点的字符串。显然，可以接受的字符串一定是母串的一个子串。而如果这个字符串是母串的一个后缀，则称它的终止节点为可接受的节点。
节点性质
- 每个节点所表示的所有字符串，一定是母串的某个前缀的若干个长度相差1的后缀。
例如，对于字符串abcabcabc，它的一个前缀是abcab，某个节点所表示的子串可能是cab、bcab、abcab。 - 节点$v$所表示的所有字符串中，定义最短的子串为$\min(v)$，最长的子串为$\max(v)$。
例如，对于字符串abcabcabc，某个节点$v$所表示的子串可能是cab、bcab、abcab，因此，$\min(v) = \mathtt{cab}, \max(v) = \mathtt{abcab}$。 - 节点$v$所表示的最长字符串在母串中的所有出现位置的结尾下标构成该节点的$\mathrm{endpos}(v)$集合。
例如，对于字符串abcabcabc，某个节点$v$所表示的子串可能是cab、bcab、abcab，因此，$\mathrm{endpos}(v) = \{ 5, 8 \}$。 - 任意两个节点的$\mathrm{endpos}(v)$集合不同。
如果存在两个节点的$\mathrm{endpos}(v)$集合相同，则说明这两个节点的出边是等价的，这两个节点可以合并使得DAWG更简化。 - 只有表示整个母串的节点沿后缀链接向上到起始节点的路径上的点的$\mathrm{endpos}(v)$集合包含母串的末尾，所有只有这些节点才是接受节点，分别代表母串的一个或一些后缀。
转移边
节点$u$到$v$有转移边，表示$u$代表的所有子串加上转移边对应的字符后，得到的集合是$v$代表的子串集合的子集，但是，并不保证两个集合相等。
后缀链接与前缀树（又称parent树）
- $u$的后缀链接指向$v$，记作$\mathrm{next}(u)=v$，当且仅当$|\min(u)|=|\max(v)|+1$且$v$代表的子串均为$u$子串的后缀。
例如，对于字符串abcabcabc，一个节点$u$可能代表子串abca、bca、ca，一个节点$v$可能代表子串a，则存在后缀链接$\mathrm{next}(u)=v$。 - 任意节点沿后缀链接的方向走，最终都会走到DAWG的起始节点，以后缀链接为边，所有的节点构成了一棵向根的有向树，称为前缀树（parent树），DAWG的起始节点是前缀树的根。
- 前缀树中，子节点的$\mathrm{endpos}(v)$集合一定是其父节点的真子集，即$\mathrm{endpos}(v) \subsetneq \mathrm{endpos}(\mathrm{next}(v))$。
因为$\max(\mathrm{next}(v))$一定是$\max(v)$的后缀，所以$\max(v)$出现的地方也会出现$\max(\mathrm{next}(v))$，所以$\mathrm{endpos}(v) \subseteq \mathrm{endpos}(\mathrm{next}(v))$。如果$\mathrm{endpos}(v) = \mathrm{endpos}(\mathrm{next}(v))$，则两个点等价可以被合并，因此$\mathrm{endpos}(v) \subsetneq \mathrm{endpos}(\mathrm{next}(v))$。 - 一个节点的$\mathrm{endpos}(v)$集合包含其所有子节点$\mathrm{endpos}(v)$集合的并，如果这个节点表示了母串的一个前缀，则还包含这个前缀的位置。
构造
流程
在字符集为常数且较小时，SAM的构造法为线性复杂度的。这是一个增量算法，因此，实际上应该解释为，每在母串后插入一个字符，更新SAM的复杂度是$O(1)$的。
这里，我们将主要使用略图结合实际例子的形式描述增量过程。
上图描述了一个串的SAM略图，我们要在这个串末尾加上字符$c$，图中，灰色的边表示字符$c$的转移边，黑色的边表示后缀链接，$\text{start}$为起始节点$\text{last}$为代表整个母串的节点。
- 从$\text{last}$点开始向上跳前缀树，直到遇到一个有字符$c$出边的节点。
图中，由于第一个有字符$c$出边的节点为$v_3$，说明对应的后缀加上字符$c$后出现在原母串中了，因此，$v_4, v_5, v_6$这些代表$v_3$代表的字符串的后缀的节点对应的后缀，加上字符$c$后也会在原母串中出现。
对于末尾那些没有字符$c$出边的节点，他们对应的较长后缀加上字符$c$后会形成新的后缀，这些后缀需要一个点来表示，因此，这些点均需要引出一条字符$c$的转移边，指向新建的后缀节点。对于新节点$u$，有$\max(u)=\max(v_1)+c, \min(u)=\min(v_2)+c$。
而对于前面那些有字符$c$出边的节点，对应的后缀已经被已存在的节点$d$所代表，因此它们不需要新建节点表示新后缀。
- 如果不存在有字符$c$出边的节点，即第1步跳到了null节点，则新建节点$u$的后缀链接指向起始节点$\text{start}$，即$\mathrm{next}(u) = \text{start}$。
因为新出现的这些后缀都用节点$u$表示了，即$|\min(u)|=1$，因此需要找到一个$\max(\mathrm{next}(u))=0$这样的$\mathrm{next}(u)$，自然就是起始节点$\text{start}$了。 - 如果$\max(d) = \max(v_3) + c$，则有$\mathrm{next}(u) = d$。
因为$|\max(d)|=|\max(v_3)|+1, |\min(u)|=|\min(v_2)|+1, |\max(v_3)|=|\min(v_2)|+1$，所以可以推出$|\max(d)|=|\min(v_2)|+2=|\min(u)|+1$，得出结论$u$的后缀链接指向$d$。
- 如果2、3的情况都不符合，此时一定有$|\max(d)|>|\max(v_3)|+1$。因为字符串$\max(v_3)+c$一定存在于$d$中，并且存在另一个异于$v_i$的节点$t$，满足$\mathrm{next}(t)=v_3$且$t$有连向$d$的转移边。
此时$d$不能直接作为$u$的后缀链接，因为$d$中的字符不全是$u$的后缀，这是由$t$带来的影响。因此，我们需要考虑把原来的$d$拆成两个点$o$和$n$，$n$表示长度不大于$|\max(v_3)|+1$的子串，另一个点代表$t$带来的更长的子串。显然，$n$可以继承$d$的出边，且$v_3$、$v_4$都可以转移到$n$，因此$n$表示的就是这两个节点的字符串加上字符$c$转移而来的，且$\mathrm{next}(o)=n$，$\mathrm{next}(n)=\mathrm{next}(d)$。这里借用Menci的例子，图示如下：
此时拆出来的的$n$点就可以作为$u$的后缀链接了。
例子
到这里，算法的流程就结束了，下面我们用若干个例子来加深理解。
向abc中加入a
abc的SAM结构 | abca的SAM结构 |
|---|---|
对于这个串，从代表母串的节点4上跳到第一个有字符a出边的节点即是起始节点1，因此节点4需要在下面新建节点5代表新后缀abca，并将节点5的后缀链接指向节点2，即节点1的a出边对应的节点，这是由于$len_2 = len_1 + 1$。在图中，$len$指的就是$|\max|$。
向abca中加入c
abca的SAM结构 | abca的SAM结构 |
|---|---|
首先从结尾节点5上跳，节点5、2没有字符c的出边，因此新建节点6来代表新后缀abcac与ac。节点1有字符c的出边，对应节点4，但是$len_4 \neq len_1 + 1$，因此需要对4拆点，新点为7，继承了4的出边，且从4上跳前缀树路径上所有指向4的边都应改为指向7。此时，6和4的后缀链接指向7，7继承了原来4的后缀链接指向1，完成构造。
实现
实现可以参考后文例题中的代码。
实现中，只需记下每个节点的$|\max|$即可，因为$|\min(u)| = |\max(\mathrm{next}(u))| + 1$。
例题：【P3804】【模板】后缀自动机 – 洛谷
题目描述
给定一个只包含小写字母的字符串 S ，请你求出 S 的所有出现次数不为 1 的子串的出现次数乘上该子串长度的最大值。
题解思路
出现次数不为1的子串，可以求出每个节点的$\mathrm{endpos}$集合大小，即上文中提到的，从前缀树的子节点加和，这个过程可以使用拓扑序来做。由于我们知道前缀树的节点越深$|\max|$越大，因此可以对这个值排序后直接转移统计。对于每个$\mathrm{endpos}$集合大小大于1的节点计算其$|\mathrm{endpos}||\max|$值更新答案即可。
代码
// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1; register char c = fgc();
for (; !isdigit(c); c = fgc()) if (c == '-') neg = -1;
for (; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
return res * neg;
}
const int MAXN = 1000005;
struct SuffixAutomaton {
int last, tot, ch[MAXN << 1][26], nxt[MAXN << 1], len[MAXN << 1], siz[MAXN << 1];
SuffixAutomaton() {
last = tot = 1;
}
inline void extend(int c) {
int u = ++tot, v = last;
len[u] = len[v] + 1;
for(; v && !ch[v][c]; v = nxt[v]) ch[v][c] = u;
if(!v) {
nxt[u] = 1;
} else if(len[ch[v][c]] == len[v] + 1) {
nxt[u] = ch[v][c];
} else {
int n = ++tot, o = ch[v][c]; len[n] = len[v] + 1;
memcpy(ch[n], ch[o], sizeof(ch[o]));
nxt[n] = nxt[o]; nxt[o] = nxt[u] = n;
for(; v && ch[v][c] == o; v = nxt[v]) ch[v][c] = n;
}
last = u; siz[u] = 1;
}
} sam;
char str[MAXN];
int a[MAXN << 1], c[MAXN << 1];
int main() {
scanf("%s", str + 1);
for(int i = 1; str[i]; i++) {
sam.extend(str[i] - 'a');
}
LL ans = 0;
for(int i = 1; i <= sam.tot; i++) c[sam.len[i]]++;
for(int i = 1; i <= sam.tot; i++) c[i] += c[i - 1];
for(int i = 1; i <= sam.tot; i++) a[c[sam.len[i]]--] = i;
for(int i = sam.tot; i; i--) {
int p = a[i];
sam.siz[sam.nxt[p]] += sam.siz[p];
if(sam.siz[p] > 1) ans = std::max(ans, 1ll * sam.siz[p] * sam.len[p]);
}
printf("%lld", ans);
return 0;
}
其他
大字符集、不确定字符集的处理方法
可以用一个map<int, int>来代替二维数组ch，这样，构造算法的复杂度就会变为$O(n \log n)$。
拓扑序
在例题中提到了，按照$|\max|$从大到小排序可以得到前缀树的拓扑序。这个排序可以使用计数排序，实现线性复杂度。
常见应用
本质不同子串数量
每个节点$u$表示的字符串长度在$[|\min(u)|, |\max(u)|]$范围内，而且每个节点代表的字符串又各不相同，因此对$\max(u)-\min(u)+1$求和即可。
字符串的最小表示法
对于字符串$S$，它的最小表示定义为，将$S$的一个前缀切去并连接在末尾，这样得到的字典序最小的字符串。
求最小表示可以先对$S+S$建立SAM，并从起始节点开始，每次沿着存在的最小字符转移边走，走$|S|$步后，路径对应的字符串即为最小表示。
求两个串的LCS
对其中一个字符串建SAM，记录一个当前匹配的长度$L$和当前走到的节点$v$，枚举另一个字符串的每个字符$c$，如果当前节点有$c$的出边，则沿出边走一步，对$L$加1；否则，跳至$\mathrm{next}(v)$，并将$L$重置为$|\max(\mathrm{next}(v))$，再次检查是否有$c$的出边，做出选择即可。
