常见字符串算法 II：自动机相关

建议先学习确定有限状态自动机，上接。

基本定义与约定：

称字符串 \(T\) 匹配 \(S\) 为 \(T\) 在 \(S\) 中出现。
模式串：相当于题目给出的 “字典”，是用于匹配的字符串。下文也称为单词。
文本串：即被匹配的字符串。
更多约定见常见字符串算法 I.

0. change log

2021.12.25. 新增 ACAM 部分。
2021.12.26. 新增 SAM 部分。

1. AC 自动机 ACAM

前置知识：Trie 树与算法。

AC 自动机是一类 DFA，全称为 Aho-Corasick automaton，简称 ACAM。

1.1. 算法详解

AC 自动机用于解决多模式串匹配问题：形如给定字典 \(s_i\) 和文本串 \(t\)，求每个单词在 \(t\) 中出现的次数（当然，实际应用远超这一基本问题）。ACAM 与 KMP 的不同点在于后者仅有一个模式串，而前者有多个模式串。

朴素的用 KMP 实现的暴力时间复杂度为 \(|t|\times N + \sum |s_i|\)，其中 \(N\) 是单词个数。这是因为进行一次匹配的时间复杂度为 \(|s_i| + |t|\)。当单词数量 \(N\) 很大的时候显然无法接受。

多串匹配自然首先考虑建出字典树。根据定义，字典树上任意结点与所有 \(s_i\) 的某个前缀一一对应，设结点（也称状态）\(i\) 所表示的字符串为 \(t_i\)。借鉴 KMP 的思想，考虑对于每个状态 \(q\in Q\) 其中 \(Q\) 是状态集合也即 trie 树上的所有结点，求出其失配指针 \(fail_q\)。这里失配指针的含义为 \(q\) 所表示字符串 \(t_q\) 的最长真后缀 \(t_q[j,|t_q|]\ (2\leq j\leq |t_q|+1)\) 使得该后缀作为某个 \(s_i\) 的前缀出现（这说明 \(t_q[j,|t_q|]\) 也对应了 trie 树上的一个状态），从 \(q\) 向字符串 \(t_q[j,|t_q|]\) 所对应的状态 \(q’\) 连一条有向边。

例如当 \(s = \{\texttt{b},\ \texttt{ab}\}\) 时，\(\tt ab\) 所表示状态会向 \(\tt b\) 所表示状态连边，因为 \(\tt ab\) 最长的（也是唯一的）在 \(s_i\) 中作为前缀出现的后缀为 \(\tt b\)。再例如当 \(s = \{\texttt{aba},\ \texttt {baba}\}\) 时，\(\tt ab\) 会向 \(\tt b\) 连边， \(\tt bab\) 会向 \(\tt ab\) 连边，\(\tt aba\) 会向 \(\tt ba\) 连边，而 \(\tt baba\) 会向 \(\tt aba\) 连边。对于每一条有向边 \(q\to q’\)，后者是前者的后缀，也是 \(s_i\) 的一个前缀。

考虑用类似 KMP 的算法求得失配指针：令 \(fail_q\gets fail_{fa_q}\)。若当前的 \(fail_q\) 没有 \(fa_q\to q\) 这条字典树上的边所表示的字符 \(c\) 的转移，则令 \(fail_q\gets fail_{fail_q}\)，否则 \(fail_q\) 即为 \(\mathrm{trans}(fail_q, c)\)，即字典树上在 \(fail_q\) 处添加字符 \(c\) 后到达的子状态，在代码中即 son[fail[q]][c]。

失配指针已经足够强大了，但这并不是 AC 自动机的完全体。既然叫自动机，那么对于每个状态的每个字符转移 \(\delta(i, c)\)，都应该封闭在状态集合 \(Q\) 里面。我们把 KMP 自动机的转移拎出来观察：

\[\delta(i, c) = \begin{cases} i+1 & s_{i + 1} = c \\ 0 & s_{i + 1} \neq c \land i = 0 \\ \delta(nxt_i, c) & s_{i + 1} \neq c \land i \neq 0 \\ \end{cases} \]

类似的，设字典树的根为结点 \(0\)，AC 自动机的转移可以写为：

\[\delta(i,c) = \begin{cases} \mathrm{trans}(i, c) & \mathrm{if}\ \mathrm{trans}(i, c)\ \mathrm{exist} \\ 0 & \mathrm{if}\ \mathrm{trans}(i, c)\ \mathrm{doesn't\ exist} \land i = 0\ (\mathrm{which\ is \ root}) \\ \delta(fail_i, c) & \mathrm{if}\ \mathrm{trans}(i, c)\ \mathrm{doesn't\ exist} \land i \neq 0 \end{cases} \]

其中 \(\delta(i,c)\) 表示往状态 \(i\) 后添加字符 \(c\)，所得字符串的最长的与 \(s_i\) 前缀匹配的后缀所表示的状态，可以类比 KMP 的最长真前缀后缀理解。

性质：当 \(\mathrm{trans}(i, c)\) 存在时，设其为 \(q\)，则有 \(fail_q = \delta(fail_i, c)\)。这一点结合 \(fail_i\) 的最长性也好理解：向 \(i\) 添加字符 \(c\) 得到的状态的失配指针等于 \(i\) 的失配指针添加 \(c\) 得到的状态，因为若 \(q\) 的失配指针比 \(\delta(fail_i, c)\) 更长，那么 \(\delta(fail_i, c)\) 总可以变得和 \(q\) 的失配指针一样长，与 \(\delta\) 的最大性矛盾。简单地说，就是必然有 \(|\delta(fail_i,c)|\geq |fail_q|\)，同时 \(|fail_q|\) 可以等于 \(|\delta(fail_i,c)|\)，这里在一个状态 \(q\) 两侧加上绝对值符号表示其所对应字符串长度即 \(|t_q|\)。有了这一性质，我们就不需要预先求出失配指针，而是在建造 AC 自动机的同时一并求出。

由于我们需要保证在计算一个状态的转移时，其失配指针指向的状态的转移已经计算完毕，又因为失配指针长度必然小于原串长度（需要是真后缀），故使用 BFS 建立 AC 自动机。一般形式的 AC 自动机代码如下，非常好写：

int node, son[N][S], fa[N];
void ins(string s) { // 建出 trie 树
	int p = 0;
	for(char it : s) {
		if(!son[p][it - 'a']) son[p][it - 'a'] = ++node;
		p = son[p][it - 'a'];
	}
}
void build() { // 建出 AC 自动机
	queue  q;
	for(int i = 0; i < S; i++) if(son[0][i]) q.push(son[0][i]); // 对于第一层特判一下，因为 fa[0] = 0，此处即转移的第二种情况
	while(!q.empty()) { // 求得的 son[t][i] 就是文章中的转移函数 delta(t, i) 啦，相当于把 trie 的转移函数和 AC 自动机合并起来了
		int t = q.front(); q.pop();
		for(int i = 0; i < S; i++)
			if(son[t][i]) fa[son[t][i]] = son[fa[t]][i], q.push(son[t][i]); // 转移的第一种情况：原 trie 图有 trans(t, i) 的转移
			else son[t][i] = son[fa[t]][i]; // 转移的第三种情况
	}
}

特别地，在 ACAM 上会有一些终止结点 \(p\) 表示一个单词或以一个单词结尾，即 \(p\) 对应的字符串 \(t_p\) 的某个后缀在字典 \(s_i\) 中出现。若状态 \(p\) 本身表示一个单词，即 \(t_p\in \{s_i\}\)，则称为单词结点。所有终止结点 \(p\) 组成的集合对应着 DFA 中的接受状态集合 \(F\)：ACAM 接受且仅接受以给定词典中的某一个单词结尾的字符串。

总结一下我们使用到的约定：

设 trie 树上结点（也称状态）\(i\) 所表示的字符串为 \(t_i\)。
失配指针的含义为 \(q\) 所表示字符串 \(t_q\) 的最长真后缀 \(t_q[j,|t_q|]\ (2\leq j\leq |t_q|+1)\) 使得该后缀作为某个 \(s_i\) 的前缀出现，从 \(q\) 向字符串 \(t_q[j,|t_q|]\) 所对应的状态 \(q’\) 连一条有向边。
\(\delta(i,c)\) 表示往状态 \(i\) 后添加字符 \(c\)，所得字符串的最长的与 \(s_i\) 前缀匹配的后缀所表示的状态。
在一个状态 \(q\) 两侧加上绝对值符号表示其所对应字符串长度即 \(|t_q|\)。
终止结点 \(p\) 表示一个单词或以一个单词结尾。
所有终止结点 \(p\) 组成的集合对应着 DFA 中的接受状态集合 \(F\)。
若状态 \(p\) 本身表示一个单词，即 \(t_p\in \{s_i\}\)，则称为单词结点。

1.2. fail 树的性质与应用

fail 树有着非常好的性质：

性质 1：对于一个结点 \(p\) 及其对应字符串 \(t_p\)，其在 fail 树上的子树内部所有结点 \(q\in \mathrm{subtree}(p)\)，都有 \(t_p\) 是 \(t_q\) 的后缀，且 \(t_p\) 是 \(t_q\) 的后缀当且仅当 \(q\in \mathrm{subtree}(p)\)。根据失配指针的定义易证。
性质 2：若 \(p\) 是终止结点，则 \(p\) 的子树全部都是终止结点。
性质 3：定义 \(ed_p\) 表示 \(t_p\) 作为单词的后缀数量，则 \(ed_p\) 等于在 fail 树上从 \(p\) 到根结点上单词结点的权值之和，其中单词结点 \(q\) 的权值为与 \(t_q\) 相等的单词数量（可能出现重复单词，若单词互不相同显然单词结点权值为 \(1\)）。这一点也是由失配指针的定义得到。

根据性质 3，有这样一类问题：单词有带修权值，多次询问对于某个给定的字符串 \(S\)，所有单词的权值乘以其在 \(S\) 中出现次数之和。初步转化为 fail 树上修点权以及查询从根到某个结点的权值之和。

通常来说链上求和要用到树剖，但查询有特殊性质：一个端点是根。因此，我们使用 “相对论”：与其单点修改链上求和，不如子树修改单点查询。实时维护每个结点的答案，这样修改一个点相当于更新子树，而查询时只需要单点查询了。转化之前的问题需要树剖 + 数据结构 \(\log^2\) 维护，但转化后即可 dfs 序 + 树状数组单 \(\log\) 解决。

应用 1：设 \(s\) 是单词，在 trie 树上为状态 \(p\)。\(t\) 是文本，求 \(s\) 在 \(t\) 中的出现次数，等于 \(t\) 在 ACAM 上经过的所有结点 \(q\)，满足 fail 树上 \(p\) 在 \(q\) 到根的路径上的 \(q\) 的个数。

1.3. 应用

1.3.1. 结合动态规划

ACAM 除了能够进行字符串匹配，还常与动态规划相结合，因为它刻画了文本串与所有模式串的匹配情况。而 \(\delta\) 转移函数自然地为动态规划的转移指明了方向。因此，当遇到形如 “不能出现若干单词” 的字符串计数或最优化问题，可以考虑在 ACAM 上 DP，即将 ACAM 的状态写进 DP 的一维。

如非常经典的 P4052 [JSOI2007]文本生成器。题目要求至少包含一个单词，补集转化为求不包含任何一个单词的长为 \(m\) 的字符串数量。考虑到我们只关心当前字符串的长度与所有单词的匹配情况，设 \(f_{i,j}\) 表示长为 \(i\) 且放到所有单词建出的 ACAM 上能够转移到状态 \(j\) 的字符串数量。转移即枚举下一个字符 \(c\) 是什么，\(f_{i,j}\to f_{i+1,\delta(j,c)}\)。根据限制，需要保证 \(j\) 和 \(\delta(j,c)\) 都不是终止结点，最终答案即 \(26^m-\sum_{\\ q\in Q\land q\notin F} f_{m, q}\)。时间复杂度 \(\mathcal{O}(nm|\Sigma||s_i|)\)。

1.3.2. 结合矩阵快速幂

在上一部分的基础上，若 \(\sum |s_i|\) 很小而转移轮数非常多，可以考虑将转移写成矩阵的形式。\(\delta(p, c)\) 为我们自然地提供了转移矩阵：添加一个字符后，从状态 \(p\) 转移到 \(q\) 的方案数为 \(\sum_\limits{c} [\delta(p, c) = q]\)，即 \(A_{i, j} = \sum_\limits c [\delta(i, c) = j]\)。

具体转移方式视题目而定，矩阵乘法也可以是广义矩阵乘法，如外层为 \(\max\)，内层为 \(+\) 的矩乘，如例 XII.

1.4. 注意事项

建出字典树后 不要忘记调用 build 建出 AC 自动机！
做题时注意模式串是否可以重复。

1.5. 例题

I. P3808 【模板】AC 自动机（简单版）

注意本题同一个编号的串多次出现仅算一次，因此题目相当于求：文本串 \(t\) 在模式串 \(s_i\) 建出的 ACAM 上匹配时经过的所有结点到根的路径并上单词结点的个数。

设当前状态为 \(p\)，每次跳 \(p\) 的失配指针，加上经过结点的权值（即当前结点表示了多少个单词）并标记已经经过该结点，直到遇到一个标记结点 \(q\)，说明 \(q\) 到根的父亲都已经被考虑到。注意上述过程并不改变 \(p\)。时间复杂度线性。

const int N = 1e6 + 5;
const int S = 26;
int n, node, son[N][S], fa[N], ed[N];
string s;
void ins(string s) {
	int p = 0;
	for(char it : s) {
		if(!son[p][it - 'a']) son[p][it - 'a'] = ++node;
		p = son[p][it - 'a'];
	} ed[p]++; // 计算 ed[p]
}
void build() {
	queue  q;
	for(int i = 0; i < S; i++) if(son[0][i]) q.push(son[0][i]);
	while(!q.empty()) {
		int t = q.front(); q.pop();
		for(int i = 0; i < S; i++)
			if(son[t][i]) fa[son[t][i]] = son[fa[t]][i], q.push(son[t][i]);
			else son[t][i] = son[fa[t]][i];
	}
}
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> s, ins(s);
	int p = 0, ans = 0; cin >> s, build();
	for(char it : s) {
		int tmp = p = son[p][it - 'a'];
		while(ed[tmp] != -1) ans += ed[tmp], ed[tmp] = -1, tmp = fa[tmp]; // ed[tmp] = --1 相当于标记经过结点
	} cout << ans << endl;
	return flush(), 0;
}

II. P2292 [HNOI2004] L 语言

首先我们有个显然的 DP：设 \(f_i\) 表示 \(i\) 前缀能否理解，那么若存在 \(f_j = 1\) 并且 \(t[j + 1,i]\in D\)，则 \(f_i = 1\)。否则 \(f_i = 0\)。对 \(D\) 建出 ACAM，设 \(t[1,i]\) 跳到了状态 \(p\)，我们只需要知道 \(p\) 的哪些长度的后缀是单词，这样就可以 \(\mathcal{O}(|t||s|)\) 回答单次询问，但不够快。

注意到 \(|s|\leq 20\)，因此考虑状压，设 \(msk_p\)：若 \(p\) 的长度为 \(l\) 的后缀是单词，则 \(msk_p\) 第 \(l\) 位为 \(1\)。这样，再用 \(S\) 记录 \(f_{i - 20}\sim f_{i - 1}\) 的状态，就可以通过位运算 \(\tt AND\) 快速得到当前 \(f_i\) 的结果，并更新回 \(S\)。

时间复杂度 \(\mathcal{O}(n|s||\Sigma| + m|t|)\)，其中 \(|\Sigma|\) 表示字符集大小。

*III. P2414 [NOI2011] 阿狸的打字机

由于删去一个字符和添加一个字符对字典树大小的影响都是 \(1\)，因此尽管单词长度之和可能很大，但建出的字典树大小仅有 \(m\)。设第 \(i\) 个单词在 trie 上的结点为 \(f_i\)，根据应用 1，查询 \(x\) 在 \(y\) 中的出现次数可以在 \(y\) 到根的每个结点上打标记，查询 \(x\) 的子树内有标记的结点个数。

因此将询问离线，按 \(y\) 从小到大的顺序处理询问（这样保证了修改标记的总次数线性）配上 BIT 即可。时间复杂度线性对数。

const int N = 1e5 + 5;
const int S = 26;
int n, m, stc[N], top, node, ed[N], son[N][S]; string s;
int dn, fa[N], dfn[N], sz[N], ans[N]; vint e[N]; vpii buc[N];
int c[N]; void add(int x, int v) {while(x <= dn) c[x] += v, x += x & -x;}
int query(int x) {int s = 0; while(x) s += c[x], x -= x & -x; return s;}
void dfs(int id) {sz[id] = 1, dfn[id] = ++dn; for(int it : e[id]) dfs(it), sz[id] += sz[it];}
int main() {
	cin >> s >> m;
	for(int i = 0, p = 0; i < s.size(); i++) {
		if(s[i] == 'P') {ed[++n] = p; continue;}
		if(s[i] == 'B') {p = stc[--top]; continue;}
		if(!son[p][s[i] - 'a']) son[p][s[i] - 'a'] = ++node;
		stc[++top] = p = son[p][s[i] - 'a'];
	} for(int i = 1, x, y; i <= m; i++) cin >> x >> y, buc[y].pb(x, i);
	queue  q; for(int i = 0; i < S; i++) if(son[0][i]) q.push(son[0][i]);
	while(!q.empty()) {
		int t = q.front(); q.pop(), e[fa[t]].pb(t);
		for(int i = 0; i < S; i++) son[t][i] ? (q.push(son[t][i]), fa[son[t][i]] = son[fa[t]][i]) : son[t][i] = son[fa[t]][i];
	} dfs(0), top = 0;
	for(int i = 0, p = 0, n = 0; i < s.size(); i++) {
		if(s[i] == 'P') for(pii it : buc[++n]) {int q = ed[it.fi]; ans[it.se] = query(dfn[q] + sz[q] - 1) - query(dfn[q] - 1);}
		else if(s[i] == 'B') add(dfn[p], -1), p = stc[--top];
		else stc[++top] = p = son[p][s[i] - 'a'], add(dfn[p], 1);
	} for(int i = 1; i <= m; i++) cout << ans[i] << "\n";
	return flush(), 0;
}

IV. P5357 【模板】AC 自动机（二次加强版）

根据 fail 树的性质 1，我们将文本串 \(S\) 在 AC 自动机上每经过一个结点就将其权值增加 \(1\)，则每个单词 \(T_i\) 在 \(S\) 中的出现次数即 \(T_i\) 在 fail 树上的子树结点权值和。一遍 dfs 即可，时间复杂度线性对数。

*V. P4052 [JSOI2007]文本生成器

ACAM 与 DP 相结合的例题。

VI. P3041 [USACO12JAN]Video Game G

非常套路的 ACAM 上 DP：设 \(f_{i, j}\) 表示长度为 \(i\) 且在 ACAM 上转移到状态 \(j\) 的字符串的最大权值，显然有转移 \(f_{i, j} + ed_{\delta(j, c)} \to f_{i + 1,\delta(j, c)}\)。时间复杂度 \(\mathcal{O}(nk|s_i||\Sigma|)\)。

*VII. CF1202E You Are Given Some Strings...

还算有趣的一道题目。对于同时与两个字符串相关的问题，考虑在拼接处计算贡献，即求出 \(f_i\) 表示有多少单词是 \(t[1,i]\) 的后缀，\(g_i\) 表示有多少单词是 \(t[i,]\) 的前缀。\(f_i\) 和 \(g_i\) 都可以用 ACAM 求出，后者只需将单词翻转即可。最终答案显然为 \(\sum_{\\i = 2} ^ {|t|} f_{i - 1} g_i\)，时间复杂度线性。

VIII. CF163E e-Government

裸题。对 \(s\) 建出 ACAM，根据应用 1，使用性质 3 部分所给出的技巧：单点修改链上求和（前提是一个端点为树根）转化为子树修改单点求和，BIT 维护即可。时间复杂度线性对数。

*IX. P7456 [CERC2018] The ABCD Murderer

由于单词可以重叠（否则就不可做了），我们只需求出对于每个位置 \(i\)，以 \(i\) 结尾的最长单词的长度 \(L_i\)，因为对于相同的出现位置，用更短的单词去代替最长单词并不会让答案更优。使用 ACAM 即可求出 \(L_i\)。

最优化问题考虑 DP：设 \(f_i\) 表示拼出 \(s[1,i]\) 的最小代价。不难得到转移 \(f_i = \min_{\\j = i - L_i} ^ {i - 1} f_j\)。特别的，若 \(L_i\) 不存在（即没有单词在 \(s\) 中以 \(i\) 为结束位置出现）则 \(f_i\) 为无穷大。若 \(f_n\) 为无穷大则无解。这可以通过线段树解决。

如果不想写线段树，还有一种方法：从后往前 DP。这样，每个位置可以转移到的地方是固定的（\(i-L_i\sim i - 1\)），所以用小根堆维护，懒惰删除即可。时间复杂度均为线性对数。

X. P3121 [USACO15FEB]Censoring G

非常经典的 AC 自动机题目。对 \(t\) 建出 SAM 加速匹配，每次加入一个字符，用栈在线维护字符串 \(s\) 即可。时间复杂度线性。

XI. P3715 [BJOI2017]魔法咒语

XII. CF696D Legen...

非常套路地设 \(f_{i, j}\) 表示长度为 \(i\) 且 ACAM 上状态为 \(j\) 时的最大贡献，令 \(ed_i\) 表示状态 \(i\) 所有后缀对应的所有单词权值之和，即不停跳 \(\mathrm{fail}\) 到达的所有结点权值之和，一个 trie 树上结点的权值为其所表示的所有单词权值之和。

显然有转移：\(f_{i, j} + ed_{\delta(j, c)}\to f_{i + 1, \delta(j, c)}\)，使用矩阵快速幂优化即可。时间复杂度 \(\mathcal{O}((\sum |s_i|) ^ 3\log L)\)。

2. 后缀自动机 SAM

后缀自动机全称 suffix automaton，简称 SAM，是一类极其有用但难以真正理解的字符串后缀结构。很久以前学习的算法，现在进行复习并重构学习笔记，看看能不能悟到一些新的东西。

2.1. 基本定义与引理

SAM 相关的定义非常多，需要牢记并充分理解它们，否则学习 SAM 会非常吃力，因为符号化的语言相较于直观的图片和实例更难以理解。

首先，我们给出 SAM 的定义：一个长为 \(n\) 的字符串 \(s\) 的 SAM 是一个接受 \(s\) 的所有后缀的最小的有限状态自动机。具体地，SAM 有状态集合 \(Q\)，每个状态是有向无环图上的一个结点。从每个状态出发有若干条或零条转移边，每条转移边都对应一个字符（因此，一条路径表示一个字符串），且从一个状态出发的转移互不相同。根据 DFA 的定义，SAM 还存在终止状态集合 \(F\)，表示从初始状态 \(T\) 到任意终止状态的任意一条路径与 \(s\) 的一个后缀一一对应。

SAM 最重要，也是最基本的一个性质：从 \(T\) 到任意状态的所有路径与 \(s\) 的所有子串一一对应。我们称状态 \(p\) 表示字符串 \(t_p\)，当且仅当存在一条 \(T\to p\) 的路径使得该路径所表示的字符串为 \(t_p\)，根据上述性质，\(t_p\) 是 \(s\) 的子串。

定义转移边 \(p\to q\) 表示的字符为 \(c_{p,q}\)。
定义 \(\delta(p,c)\) 表示状态 \(p\) 添加字符 \(c\) 转移到的状态。
定义前缀状态集合 \(P\) 由所有 \(s[1, i]\) 对应的状态组成。

\(\mathrm{endpos}(t)\)：字符串 \(t\) 在 \(s\) 中所有出现的结束位置的集合。例如当 \(s=\texttt{"abcab"}\) 时，\(\mathrm{endpos}(\texttt{"ab"})=\{2,5\}\)，因为 \(s[1 : 2] = s[4 : 5] = \texttt{"ab"}\)。
\(\mathrm{substr}(p)\)：状态 \(p\) 所表示的所有子串的集合。
\(\mathrm{shortest}(p)\)：状态 \(p\) 所表示的所有子串中，长度最短的那一个子串。
\(\mathrm{longest}(p)\)：状态 \(p\) 所表示的所有子串中，长度最长的那一个子串。
\(\mathrm{minlen}(p)\)：状态 \(p\) 所表示的所有子串中，长度最短的那一个子串的长度。\(\mathrm{minlen}(i)=|\mathrm{shortest}(i)|\)。
\(\mathrm{len}(i)\)：状态 \(p\) 所表示的所有子串中，长度最长的那一个子串的长度。\(\mathrm{len}(i)=|\mathrm{longest}(i)|\)。

两个字符串 \(t_1,t_2\) 的 \(\mathrm{endpos}\) 可能相等。例如当 \(s = \texttt{"abab"}\) 时，\(\mathrm{endpos}(\texttt{"b"}) = \mathrm{endpos}(\texttt{"ab"})\)。这样，我们可以将 \(s\) 的子串划分为若干等价类。SAM 上的每个状态对应若干 \(\mathrm{endpos}\) 集合相同的子串。换句话说，\(\forall t\in \mathrm{substr}(p)\)，\(\mathrm{endpos}(t)\) 相等。因此，SAM 的状态数等于所有子串的等价类个数（初始状态对应空串）。

读者应该有这样的直观印象：SAM 上的每个状态 \(p\) 都表示一个独一无二的 \(\mathrm{endpos}\) 等价类，它对应着在 \(s\) 中出现位置相同的一些子串 \(\mathrm{substr}(p)\)。\(\mathrm{shortest}(p),\mathrm{longest}(p),\mathrm{minlen}(p)\) 和 \(\mathrm{len}(p)\) 描述了 \(\mathrm{substr}(p)\) 最短和最长的子串及其长度。

转移边与 \(\mathrm{substr}\) 的联系：任意一条 \(T\to p\) 的路径所表示的字符串 \(t_p\in \mathrm{substr}(p)\)。

在引出 SAM 的核心定义「后缀链接」前，我们需要证明关于上述概念的一些性质。下列引理的内容部分来自 OI-wiki，相关链接见 Part 2.4.

引理 1：考虑两个非空子串 \(u\) 和 \(w\)（假设 \(|u|\leq |w|\)）。要么 \(\mathrm{endpos}(u)\cup \mathrm{endpos}(w)=\varnothing\)，要么 \(\mathrm{endpos}(w) \subseteq \mathrm{endpos}(u)\)，取决于 \(u\) 是否为 \(w\) 的一个后缀：

\[\begin{cases} \mathrm{endpos}(w) \subseteq \mathrm{endpos}(u) & \mathrm{if} \ u\ \mathrm{is\ a\ suffix\ of}\ w \\ \mathrm{endpos}(u) \cup \mathrm{endpos}(w) = \varnothing & \mathrm{otherwise} \end{cases} \]

证明：若存在位置 \(i\) 满足 \(i\in \mathrm{endpos}(u)\) 且 \(i\in \mathrm{endpos}(w)\)，说明 \(u\) 和 \(w\) 以 \(i\) 为结束位置在 \(s\) 中出现。由于 \(|u|\leq |w|\)，所以 \(u\) 必然是 \(w\) 的后缀，因此 \(w\) 出现的位置 \(u\) 必然以 \(w\) 的后缀形式出现，即对于任意 \(i\in \mathrm{endpos}(w)\) 有 \(i\in \mathrm{endpos}(u)\)。否则不存在这样的位置 \(i\)，即 \(\mathrm{endpos}(u) \cup \mathrm{endpos}(w) = \varnothing\)。

引理 2：考虑一个状态 \(p\)。\(p\) 所表示的所有子串长度连续，且较短者总是较长者的后缀。

证明：根据引理 1，若两个子串 \(\mathrm{endpos}\) 相同（这也意味着它们属于相同状态），则较短者总是较长者的后缀，后半部分得证。

对于前半部分考虑反证：假设 \(\mathrm{longest}(p)\) 长为 \(L\ (\mathrm{minlen}(p) < L < \mathrm{len}(p))\) 的后缀 \(t_L\notin \mathrm{substr}(p)\)。由于 \(t_L\) 是 \(\mathrm{longest}(p)\) 的真后缀，故 \(\mathrm{endpos}(\mathrm{longest}(p)) \subseteq \mathrm{endpos}(t_L)\)。根据假设，\(\mathrm{endpos}(\mathrm{longest}(p)) \neq \mathrm{endpos}(t_L)\)。又因为 \(\mathrm{shortest}(p)\) 是 \(t_L\) 的真后缀，故 \(\mathrm{endpos}(t_L) \subseteq \mathrm{endpos}(\mathrm{shortest}(p))\)，因此 \(|\mathrm{endpos}(\mathrm{longest}(p))| < |\mathrm{endpos}(t_L)| \leq |\mathrm{endpos}(\mathrm{shortest}(p))|\)，这与 \(\mathrm{endpos}(\mathrm{longest}(p)) = \mathrm{endpos}(\mathrm{shortest}(p))\) 矛盾，证毕。

简单地说，对于一个子串 \(t\) 的所有后缀，其 \(\mathrm{endpos}\) 集合大小随着后缀长度减小而单调不降。这很好理解，后缀越长，在 \(s\) 中出现的位置就越少。

推论 1：对于子串 \(t\) 的所有后缀，其 \(\mathrm{endpos}\) 集合大小随后缀长度减小而单调不降，且较小的 \(\mathrm{endpos}\) 集合包含于较大的 \(\mathrm{endpos}\) 集合。

引理 2 是非常重要的性质。有了它，我们就可以定义后缀链接了。

定义状态 \(p\) 的后缀链接 \(\mathrm{link}(p)\) 指向 \(\mathrm{longest}(p)\) 最长的一个后缀 \(w\) 满足 \(w\notin \mathrm{substr}(p)\) 所在的状态。换句话说，一个后缀链接 \(\mathrm{link}(p)\) 连接到对应于 \(\mathrm{longest}(p)\) 最长的处于另一个 \(\mathrm{endpos}\) 等价类的后缀所在的状态。根据引理 2，我们有\(\mathrm{minlen}(i)=\mathrm{len(link}(i))+1\)。

引理 3：所有后缀链接形成一棵以 \(T\) 为根的树。

证明：对于任意不等于 \(T\) 的状态，沿着后缀链接移动总能达到一个所表示字符串更短的状态，直到 \(T\)。

定义后缀路径 \(p\to q\) 表示在后缀链接形成的树上 \(p\to q\) 的路径。

引理 4：通过 \(\mathrm{endpos}\) 集合构造的树（每个子结点的 \(\mathrm {subset}\) 都包含在父结点的 \(\mathrm{subset}\) 中）与通过后缀链接 \(\mathrm{link}\) 构造的树相同。

根据推论 1 与后缀链接的定义容易证明。因此，后缀链接构成的树本质上是 \(\mathrm{endpos}\) 集合构成的一棵树。

上图图源 OI-wiki。我们给出每个状态的 \(\mathrm{endpos}\) 集合以便更好理解引理 4：\(\mathrm{endpos}(\texttt{"a"}) = \{1\}\)，

\[\begin{aligned} \mathrm{endpos}(\texttt{"ab"}) = \{2\} \\ \mathrm{endpos}(\texttt{"abcb","bcb","cb"}) = \{4\} \\ \end{aligned} \subsetneq \mathrm{endpos}(\texttt{"b"}) = \{2,4\} \\ \]

\[\begin{aligned} \mathrm{endpos}(\texttt{"abc"}) = \{3\} \\ \mathrm{endpos}(\texttt{"abcbc","bcbc","cbc"}) = \{5\} \\ \end{aligned} \subsetneq \mathrm{endpos}(\texttt{"bc","c"}) = \{3,5\} \\ \]

2.2. 关键结论

我们还需要以下定理确保构建 SAM 的算法的正确性，并使读者对上述定义形成感性的直观的认知。

结论 1.1：从任意状态 \(p\) 出发跳后缀链接到 \(T\) 的路径，所有状态 \(q\in p\to T\) 的 \([\mathrm{minlen}(q),\mathrm{len}(q)]\) 不交，单调递减且并集形成连续区间 \([0,\mathrm{len}(p)]\)。

证明：根据后缀链接的性质 \(\mathrm{len}(\mathrm{link}(p)) + 1 = \mathrm{minlen}(p)\) 即证。

结论 1.2：从任意状态 \(p\) 出发跳后缀链接到 \(T\) 的路径，所有状态 \(q\in p\to T\) 的 \(\mathrm{substr}(q)\) 的并集为 \(\mathrm{longest}(p)\) 的所有后缀。

证明：由结论 1.1 和后缀链接的定义易证。

结论 2.1：\(\forall t_p\in \mathrm{substr}(p)\)，若存在 \(p\to q\) 的转移边，则 \(t_p + c_{p,q}\in \mathrm{substr}(q)\)。

证明：根据 \(\mathrm{substr}\) 的定义可得。

结论 2.2：\(\forall t_q\in \mathrm{substr}(q)\) 若存在 \(p\to q\) 的转移边，则 \(\exist t_p\in \mathrm{substr}(p)\) 使得 \(t_p+c_{p,q} = t_q\)。

证明：结论 2.1 的逆命题。这很好理解，因为对于任意 \(t_q\in \mathrm{substr}(q)\)，若不存在这样的 \(t_p + c_{p,q} = t_q\)，那么就不存在 \(T\to q\) 的路径使得其所表示字符串为 \(t_p + c_{p,q}\)，这与 \(t_q\in \mathrm{substr}(q)\) 矛盾。

结论 3.1：考虑状态 \(q\)，不存在转移 \(p\to q\) 使得 \(\mathrm{len}(p) + 1 > \mathrm{len}(q)\)。

证明：显然。

结论 3.2：考虑状态 \(q\)，唯一存在转移 \(p\to q\) 使得 \(\mathrm{len}(p) + 1 = \mathrm{len}(q)\)。

证明：考虑反证法，若不存在这样的 \(p\)，说明 \(\forall p,\mathrm{len}(p)+1<\mathrm{len}(q)\)。根据结论 2.2，\(\mathrm{substr}(q)\) 中最长的一个串的长度为 \(\max_{\\ t_p\in \mathrm{substr}(p)} |t_p| + 1\) 即 \(\max_{\\ p} \mathrm{len}(p) + 1\)。根据 \(\mathrm{len}\) 的定义与 \(\mathrm{len}(p) + 1 < \mathrm{len}(q)\)，推得 \(\mathrm{len}(q) < \mathrm{len}(q)\)，矛盾。唯一性不难证明。

简单地说，若数集 \(T\) 由若干数集 \(S\) 的并加上 \(1\) 后得到，那么 \(\max_{\\ s\in S}s + 1 = \max_{\\ t\in T}t\)。

结论 3.3：考虑状态 \(q\)，唯一存在转移 \(p\to q\) 使得 \(\mathrm{minlen}(p) + 1 = \mathrm{minlen}(q)\)。

证明：同理。

定义 \(\mathrm{maxtrans}(q)\) 表示使得 \(\mathrm{len}(p) + 1 = \mathrm{len}(q)\) 且存在转移 \(p\to q\) 的唯一的 \(p\)。
定义 \(\mathrm{mintrans}(q)\) 表示使得 \(\mathrm{minlen}(p) + 1 = \mathrm{minlen}(q)\) 且存在转移 \(p\to q\) 的唯一的 \(p\)。

结论 4.1：考虑状态 \(q\)，若存在转移 \(p\to q\)，则 \(p\) 在后缀链接树上是 \(\mathrm{maxtrans}(q)\) 或其祖先。

证明：由于所有 \(p\) 转移到相同状态 \(q\)，故所有 \(p\) 的 \(\mathrm{substr}(p)\) 的并，短串为长串的后缀。根据 \(\mathrm{link}\) 树的性质即证。

结论 4.2：考虑状态 \(q\)，若存在转移 \(p\to q\)，则 \(p\) 在后缀链接树上是 \(\mathrm{mintrans}(q)\) 或其子结点。

证明：同理。

结论 4.3：考虑状态 \(q\)，若存在转移 \(p\to q\)，则所有这样的 \(p\) 在 \(\mathrm{link}\) 树上形成了一条深度递减的链 \(\mathrm{maxtrans}(q)\to \mathrm{mintrans}(q)\)。

证明：结合结论 4.1 与结论 4.2 易证。

可以发现上述性质大都与后缀链接有关，因后缀链接是 SAM 所提供的最重要的信息，是 SAM 的核心。我们甚至可以抛弃 SAM 的 DAG，仅仅使用后缀链接就可以结局大部分字符串相关问题。

扩展定义：\(\mathrm{substr}(p\to q)\) 表示 \(p\to q\) 后缀路径所有状态的 \(\mathrm{substr}\) 的并集。

2.3. 构建 SAM

铺垫了这么多，我们终于有足够的性质来建造 SAM 了。之前的长篇大论可能让读者认为它是一个非常复杂的算法：是，但不完全是（~~经典矛盾文学~~）：至少在代码实现方面比 LCT 不知道方便到哪里去了。

SAM 的构建核心思想是增量法，即我们将在 \(s[1,i-1]\) 的 SAM \(A_{i - 1}\) 的基础上进行更新，从而得到 \(s[1,i]\) 的 SAM \(A_i\)。因此，这一算法是在线算法。它主要分为三个步骤：

打开 SAM。
把字符插进去。
关上 SAM。

设 \(s[1,i - 1]\) 在 \(A_{i - 1}\) 上的状态为 \(las\)，当前状态数量为 \(cnt\)。\(las\) 和 \(cnt\) 的初始值均为 \(1\)，表示源点 \(T = 1\)，做题时千万不要忘记初始化 \(las,cnt\gets 1\)。

新建初始状态 \(cur \gets cnt + 1\)，并令 \(cnt\) 自增 \(1\) 表示状态数量增加 \(1\)。\(cur\) 即 \(s[1,i]\) 在 \(A_i\) 上对应的状态， \(\mathrm{endpos}(cur) = \{i\}\)。令变量 \(p\gets las\) 防止接下来的操作改变 \(las\)。

接下来我们考虑如何连指向 \(cur\) 的转移边：由于 \(las\to T\) 后缀路径上的所有状态表示了所有 \(s[1,i - 1]\) 的后缀，因此若 \(p\) 没有 \(s_i\) 的转移边，就新建 \(p\to cur\) 字符为 \(s_i\) 的转移，并令 \(p\gets \mathrm{link}(p)\) 表示跳后缀链接。直到我们遇到路径上第一个有 \(s_i\) 出边的状态 \(p\)，此时就应该停止了，因为再连下去 \(T\to p\to \delta(p,s_i)\) 和 \(T\to p\to cur\) 会表示相同字符串，与 SAM 的性质相违背。此时需要分三种情况讨论：

case 1：不存在 \(p\)。即后缀路径 \(las\to T\) 上所有状态都没有字符 \(s_i\) 的转移边。

容易发现这种情况仅在 \(s_i\) 未在 \(s[1:i-1]\) 中出现过时发生。我们只需令 \(\mathrm{link}(cur)\gets T\) 即可。

case 2：存在 \(p\)，令 \(q = \delta(p,s_i)\) 且 \(\mathrm{len}(p) + 1 = \mathrm{len}(q)\)。

令 \(\mathrm{link}(cur)\gets q\) 即可，原因如下：设 \(las\to T\) 后缀路径上 \(p\) 的前一个状态为 \(p'\)。根据操作，可知 \(p'\to cur\) 有一条转移边。则此时 \(\mathrm{minlen}(cur) = \mathrm{minlen}(p') + 1 = (\mathrm{len}(p) + 1) + 1 = \mathrm{len}(q) + 1\)，说明 \(q\) 恰好与 \(cur\) 的后缀链接的定义相匹配。

可以证明 \(\mathrm{substr}(q\to T)\) 是 \(s[1,i]\) 所有长度 \(\leq \mathrm{len}(q)\) 的后缀：由于 \(\mathrm{substr}(las\to T)\) 是 \(s[1,i - 1]\) 的所有后缀，又因为 \(p\) 在 \(las\to T\) 上，所以 \(\mathrm{longest}(p)\) 是 \(s[1,i-1]\) 长为 \(\mathrm{len}(p)\) 的后缀。而 \(p\to q\) 存在字符为 \(s_i\) 的转移边，故 \(\mathrm{longest}(q)\) 是 \(s[1,i]\) 长为 \(\mathrm{len}(p) + 1=\mathrm{len}(q)\) 的后缀。再根据结论 1.2 得证。这同时也证明了 \(\mathrm{link}(cur)\gets q\) 这一操作的正确性。

图源 hihocoder。上图中，在插入 \(s_5 = \texttt{a}\) 时，状态 \(p=las = 4\) 没有字符 \(\tt a\) 的转移，因此令 \(\delta(4,\texttt a ) = cur = 6\)，然后 \(p\gets \mathrm{link}(p) = 5\)。状态 \(5\) 也没有字符 \(\tt a\) 的转移，因此令 \(\delta(5,\texttt a ) = 6\)，然后 \(p\gets \mathrm{link}(p)= T\)，也就是图中的 \(S\)。

\(\delta(T,\texttt a )\) 存在，此时 \(p = T, q = \delta(T,\texttt a ) = 1\)。因为 \(\mathrm{len}(T) + 1 = \mathrm{len}(1)\)，所以令 \(\mathrm{link}(6)\gets 1\) 即可。

注意状态 \(4,5,6\) 所表示的子串，可以发现 \((\mathrm{substr}(4)\cup \mathrm{substr}(5)) + \texttt{a} = \mathrm{substr}(6)\)。这很好地验证了结论 2.1 和结论 2.2。

case 3：存在 \(p\)，令 \(q = \delta(p,s_i)\) 但 \(\mathrm{len}(p) + 1 \neq \mathrm{len}(q)\)。

此时 \(\mathrm{len}(p) + 1 < \mathrm{len}(q)\)，我们需要将 \(q\) 拆成两个状态 \(q_1\) 和 \(q_2\)，将 \(\mathrm{substr}(q)\) 分成长度小于等于 \(\mathrm{len}(p) + 1\) 和大于 \(\mathrm{len}(p) + 1\) 两部分。具体地，先令 \(cnt\gets cnt + 1\)，然后新建一个状态 \(cl \gets cnt\) 表示将 \(\mathrm{substr}(q)\) 长度 \(\leq \mathrm{len}(p) + 1\) 的部分丢给 \(cl\)：

\(\mathrm{minlen}(cl)\) 等于原来的 \(\mathrm{minlen}(q)\)。
\(\mathrm{len}(cl)\) 等于 \(\mathrm{len}(p) + 1\)。
新的 \(\mathrm{minlen}(q)\) 等于 \(\mathrm{len}(cl) + 1\)。

考虑 \(cl\) 如何继承 \(q\) 这一状态：首先，\(q\) 的所有转移要原封不动地存下来，故每个字符 \(c\) 都要 \(\delta(cl, c) \gets \delta(q, c)\)。此外，由于 \(\mathrm{minlen}(cl)\) 等于原来的 \(\mathrm{minlen}(q)\)，因此 \(\mathrm{link}(cl) \gets\) 原来的 \(\mathrm{link}(q)\)。同时，新的 \(\mathrm{minlen}(q)\) 等于 \(\mathrm{len}(cl) + 1\) 也即 \(\mathrm{len}(p) + 1\)，所以 \(\mathrm{link}(q),\mathrm{link}(cur)\gets cl\)。

此外，根据结论 4.3，我们知道后缀路径 \(p\to T\) 上转移到 \(q\) 的状态一定是路径的一段前缀，对于前缀上的所有结点 \(p’\)，我们需要把 \(\delta(p', s_i)\) 从本来的 \(q\) 改成 \(cl\)，因为我们把 \(\mathrm{substr}(q)\) 长度 \(\leq \mathrm{len}(p) + 1\) 的串丢给了状态 \(cl\)，所以对于原本能转移到 \(q\) 的所有 \(\mathrm{len}\) 值 \(\leq \mathrm{len}(p)\) 的状态（显然也是 \(p\to T\) 路径的前缀），都需要将字符 \(s_i\) 的转移重定向至 \(cl\)。

上图中，我们把 \(q = 3\) 的不大于 \(\mathrm{len}(p = T) + 1 = 1\) 的所有子串提出来，丢给一个新建的状态 \(cl=5\)，然后 \(\mathrm{link}(cur = 4)\gets cl = 5\)。内部 \(\mathrm{link}(q = 3)\gets cl = 5\)，同时 \(\mathrm{link}(cl = 5) \gets p = T\)，即原来的 \(\mathrm{link}(q)\)。

然后，从 \(p = T\) 往上跳后缀连接直到不存在连向 \(q = 3\) 的路径或到达根结点 \(T\)，表示对于 \(p\to T\) 的一段前缀，满足前缀上所有状态添加字符 \(s_i\) 能够转移到 \(q = 3\)，将它们字符为 \(s_i\) 的转移重定向至 \(cl = 5\)（当然，上例只有 \(T\) 一个点，不过并不一定会跳到 \(T\)，因为可能跳到中间的某个状态 \(p'\) 时就没有转移 \((p',q = 3)\) 了），即 \((T,3)\) 变为了 \((T,5)\)。

上述分类讨论结束后，令 \(las\gets cur\) 表示添加字符 \(s_{i+1}\) 时 \(s[1,i]\) 在 \(A_i\) 对应状态 \(cur\)。在实现中，我们通常在连接转移边之前执行该操作。构建 SAM 的代码如下：

const int N = 1e5 + 5;
const int S = 26;
int cnt = 1, las = 1, son[N][S], fa[N], len[N];
void ins(char s) {
	int it = s - 'a', p = las, cur = ++cnt;
	len[cur] = len[p] + 1, las = cur; // 计算 len[cur]，更新 las
	while(!son[p][it]) son[p][it] = cur, p = fa[p]; // 添加转移边
	if(!p) return fa[cur] = 1, void(); // case 1 
	int q = son[p][it];
	if(len[p] + 1 == len[q]) return fa[cur] = q, void(); // case 2
	int cl = ++cnt; cpy(son[cl], son[q], S); // 新建结点，cl 继承 q 的所有转移
	len[cl] = len[p] + 1, fa[cl] = fa[q], fa[q] = fa[cur] = cl; // 计算 len[cl] 以及 cl, q, cur 的后缀链接，注意 fa[cl] = fa[q] 要在 fa[q] = cl 之前
	while(son[p][it] == q) son[p][it] = cl, p = fa[p]; // 修改后缀路径 p -> T 的一段前缀
}

当字符集 \(\Sigma\) 非常大的时候，时空复杂度均无法接受，因此需要使用平衡树维护每个状态的所有转移边，可以用 map 代替。

2.4. 时间复杂度证明

下设字符串 \(s\) 长度为 \(n\)，证明大部分摘自 OI wiki。

构建后缀自动机的算法本身就已经证明了其 SAM 状态数不超过 \(2n-1\)：插入 \(s_1,s_2\) 时分别产生一个状态，后续插入每个 \(s_i\) 时最多产生两个状态，因此当 \(n>1\) 时状态数不超过 \(2n-2\)，形如 \(\tt abb\cdots bb\) 的字符串达到上界。当 \(n=1\) 时状态数为 \(2n-1\)。

称 \(\mathrm{len}(p) + 1 = \mathrm{len}(q)\) 的转移 \((p, q)\) 为连续的，显然，从一个非终止状态 \(p\) 出发有且仅有一条连续转移 \((p,q)\)，对于 \(q\) 也有且仅有一个对应的 \(p\)。因此，连续转移总数不超过 \(2n-2\)。对于不连续的转移，找到从根结点 \(T\to p\) 的一条连续路径，设其所表示字符串为 \(u\)；找到从 \(q\) 到任意一个终止结点 \(f\in F\) 的一条连续路径，设其所表示字符串为 \(v\)。对于不同的 \(p,q\)，\(s_{p,q} = u + c_{p,q} + v\) 互不相同：若两个转移 \((p,q)\) 和 \((p', q')\) 出现 \(s_{p, q} = s_{p', q'}\) 的情况，由于不同路径所表示字符串不同，因此 \((p, q)\) 和 \((p', q')\) 在同一条路径，这与 \(T\to p\) 和 \(q\to F\) 连续矛盾。又因为 \(s_{p, q}\) 是 \(s\) 的真后缀（\(s\) 对应的路径转移显然连续），因此不连续的转移数量不超过 \(n-1\)。这样，我们得到了转移数上界 \(3n-3\)。

2.5. 应用

2.5.1. 求本质不同子串个数

根据 SAM 的性质，每个子串唯一对应一个状态，因此答案即 \(\sum \mathrm{len}(i) - \mathrm{len}(\mathrm{link}(i))\)。

2.5.2. 字符串匹配

用字符串 \(t\) 在 \(s\) 的 SAM 上跑匹配时，我们可以得到对于 \(t\) 的每个前缀 \(t[1, i]\)，其作为 \(s\) 的子串出现的最长后缀 \(L_i\)：若当前状态 \(p\)（即 \(t[i - L_{i - 1}, i - 1]\) 所表示的状态）不能匹配 \(t_i\)（即 \(\delta(p, t_i)\) 不存在），就跳后缀链接令 \(p\gets \mathrm{link}(p)\) 并实时更新 \(L_i = \mathrm{len}(p)\) 直到 \(p = T\) 或 \(\delta(p, t_i)\) 存在，对于后者令 \(p\gets \delta(p, t_i)\)，\(L_i\) 还需再加上 \(1\)。若能匹配，则直接令 \(p\gets \delta(p, t_i)\) 并令 \(L_i\gets L_{i - 1} + 1\)。综合一下，我们得到如下代码：

for(int i = 1, p = 1, L = 0; i <= n; i++) {
	while(p > 1 && !son[p][t[i] - 'a']) L = len[p = fa[p]];
	if(son[p][t[i] - 'a']) L = min(L + 1, len[p = son[p][t[i] - 'a']]);
}

2.6. GSAM 的简便写法

GSAM 即广义 SAM，全称 General Suffix Automaton，相对于普通 SAM 它支持对多个字符串进行处理。

一般的写法是每插入一个字符串前将 \(las\) 指针置为 \(T\)，非常方便。一个细节：构建单串 SAM 时，\(\delta(las, s_i)\) 一定不存在，但对于多串 SAM 可能存在。这说明当前字符串 \(s\) 的 \(i\) 前缀是某个已经添加过的字符串的子串。我们需要进行以下特判，否则会出现这种情况：https://www.luogu.com.cn/discuss/322224 。

当 \(q = \delta(las, s_i)\) 存在，且 \(\mathrm{len}(las) + 1 = \mathrm{len}(q)\) 时，令 \(las\gets q\) 并直接返回。
当 \(q = \delta(las, s_i)\) 存在，且 \(\mathrm{len}(las) + 1 \neq \mathrm{len}(q)\) 时，我们会新建结点 \(cl\)，并进行复制。此时，令 \(las\gets cl\) 而非 \(cur\)。这是因为 \(\mathrm{len}(cur) = \mathrm{len}(las) + 1\) 且 \(\mathrm{len}(cl) = \mathrm{len}(las) + 1\)，又因为 \(\mathrm{link}(cur) = cl\)，所以这说明 \(\mathrm{substr}(cur) = \varnothing\)，即结点 \(cur\) 是空壳，真正的信息在 \(cur\) 上面。为此，我们舍弃掉这个 \(cur\)，并用 \(cl\) 代替它。

int ins(int p, int it) {
	if(son[p][it] && len[son[p][it]] == len[p] + 1) return son[p][it]; // 如果结点已经存在，且 len 值相对应，即 (p, son[p][it]) 是连续转移，则直接转移。
	int cur = ++cnt, chk = son[p][it]; len[cur] = len[p] + 1;
	while(!son[p][it]) son[p][it] = cur, p = fa[p];
	if(!p) return fa[cur] = 1, cur;
	int q = son[p][it];
	if(len[p] + 1 == len[q]) return fa[cur] = q, cur;
	int cl = ++cnt; cpy(son[cl], son[q], S);
	len[cl] = len[p] + 1, fa[cl] = fa[q], fa[q] = fa[cur] = cl;
	while(son[p][it] == q) son[p][it] = cl, p = fa[p];
	return chk ? cl : cur; // 如果 len[las][it] 存在，则 cur 是空壳，返回 cl 即可
}

上述方法本质相当于对匹配串建出 trie 后进行 dfs 构建 SAM。部分特殊题目会直接给出 trie 树而非模板串，此时模板串长度之和的级别为 \(\mathcal{O}(|S| ^ 2)\)，因此只能 bfs 构建 SAM：设 \(P_p\) 表示 trie 树上状态 \(p\) 在 SAM 上对应的位置，若 trie 树上的转移 \(q = \delta_t(p, c)\) 存在，其中 \(c\) 是字符，那么以 \(P_p\) 作为 \(las\)，插入字符 \(c\) 后新的 \(las\) 即 \(P_q\)。此时不需要像上面一样特判，因为\(\delta(P_p, c)\) 必然不存在，这是由于 \(\mathrm{len}(P_p)\) 显然单调不降。模板题 P6139 代码：

const int N = 2e6 + 5;
const int S = 26;

ll n, ans, cnt = 1;
string s;
int len[N], fa[N], son[N][S];
int ins(int p, int it) {
	int cur = ++cnt; len[cur] = len[p] + 1;
	while(!son[p][it]) son[p][it] = cur, p = fa[p];
	if(!p) return fa[cur] = 1, cur;
	int q = son[p][it];
	if(len[p] + 1 == len[q]) return fa[cur] = q, cur;
	int cl = ++cnt; cpy(son[cl], son[q], S);
	len[cl] = len[p] + 1, fa[cl] = fa[q], fa[q] = fa[cur] = cl;
	while(son[p][it] == q) son[p][it] = cl, p = fa[p];
	return cur;
}

int node = 1, pos[N], tr[N][S];
void ins(string s) {
	int p = 1;
	for(char it : s) {
		if(!tr[p][it - 'a']) tr[p][it - 'a'] = ++node;
		p = tr[p][it - 'a'];
	}
}
void build() {
	queue  q; q.push(pos[1] = 1);
	while(!q.empty()) {
		int t = q.front(); q.pop();
		for(int i = 0, p; i < S; i++) if(p = tr[t][i])
			pos[p] = ins(pos[t], i), q.push(p);
	}
}
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> s, ins(s); build();
	for(int i = 2; i <= cnt; i++) ans += len[i] - len[fa[i]];
	cout << ans << endl;
	return flush(), 0;
}

2.7. 常用技巧

2.7.1. 线段树合并维护 \(\mathrm{endpos}\) 集合

对于部分题目，我们需要维护每个状态的 \(\mathrm{endpos}\) 集合，以刻画每个子串在字符串中所有出现位置的信息。

为此，我们在 \(s[1, i]\) 对应状态的 \(\mathrm{endpos}\) 集合里插入位置 \(i\)，再根据由 \(\mathrm{endpos}\) 集合构造出来的树本质上就是后缀链接树这一事实，在 \(\mathrm{link}\) 树上进行线段树合并即可得到每个状态的 \(\mathrm{endpos}\) 集合。这是一个非常有用且常见的技巧。

特别的，如果仅为了得到 \(\mathrm{endpos}\) 集合大小，那么只需求出每个状态在 \(\mathrm{link}\) 树上的子树有多少个前缀状态 \(p\in P\) 即可。对此有两种解决方法：直接建图 dfs，以及 ——

2.7.2. 桶排确定 dfs 顺序

显然后缀链接树上父亲的 \(\mathrm{len}\) 值一定小于儿子，但千万不能认为编号小的结点 \(\mathrm{len}\) 值也小。因此，对所有结点按照 \(\mathrm{len}\) 值从大到小进行桶排序，然后按桶排后的顺序合并每个状态及其父亲是正确的，并且常数比建图 + dfs 小不少，代码见例题 I。

注意点：对于多串 SAM（GSAM），如果插入新字符串时令 \(las\gets T\) 且不特判 \(\delta(las, s_i)\) 是否存在，会导致出现空状态，从而父结点的 \(\mathrm{len}\) 值不一定严格小于子结点，使得桶排失效。对此要格外注意。

2.8. 例题

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

对 \(s\) 建出 SAM，对于每个状态 \(p\) 求出其 \(\mathrm{endpos}\) 集合大小。根据题目限制，答案即 \(\sum_{\\ \mathrm{|endpos}(p)|\geq 2}\mathrm{len}(p)\times |\mathrm{endpos}(p)|\)。视字符集大小为常数，时间复杂度线性。

const int N = 2e6 + 5; // 不要忘记开两倍空间 
int n, las = 1, cnt = 1; char s[N]; ll ans;
int len[N], fa[N], ed[N], son[N][26], buc[N], id[N];
void ins(char c) {
	int it = c - 'a', p = las, cur = ++cnt;
	las = cur, len[cur] = len[p] + 1, ed[cur] = 1;
	while(!son[p][it]) son[p][it] = cur, p = fa[p];
	if(!p) return fa[cur] = 1, void();
	int q = son[p][it];
	if(len[p] + 1 == len[q]) return fa[cur] = q, void();
	int cl = ++cnt; len[cl] = len[p] + 1;
	fa[cl] = fa[q], fa[q] = fa[cur] = cl, cpy(son[cl], son[q], 26);
	while(son[p][it] == q) son[p][it] = cl, p = fa[p];
}
int main() {
	cin >> s + 1, n = strlen(s + 1);
	for(int i = 1; i <= n; i++) ins(s[i]);
	for(int i = 1; i <= cnt; i++) buc[len[i]]++;
	for(int i = 1; i <= n; i++) buc[i] += buc[i - 1];
	for(int i = cnt; i; i--) id[buc[len[i]]--] = i; // 这部分是桶排
	for(int i = cnt; i; i--) ed[fa[id[i]]] += ed[id[i]]; // 这部分是求 endpos 集合大小
	for(int i = 1; i <= cnt; i++) if(ed[i] > 1) ans = max(ans, 1ll * ed[i] * len[i]);
	cout << ans << endl; 
	return flush(), 0;
}

II. P4070 [SDOI2016]生成魔咒

非常裸的 SAM，插入每个字符后新增的子串个数为 \(\mathrm{len}(cur) - \mathrm{len}(\mathrm{link}(cur))\)，求和即可。由于字符集太大，需要使用 map 存转移数组，时间复杂度线性对数。

*III. P4022 [CTSC2012]熟悉的文章

首先二分答案，考虑设 \(f_i\) 表示文章的 \(i\) 前缀最长的符合限制的匹配长度。根据应用 2.5.2 我们可以求出文章的每个前缀作为字典子串出现的最长后缀长度，剩下来就是单调队列解决的事情了。时间复杂度线性对数。

IV. P5546 [POI2000]公共串

建出 GSAM 后，设 \(msk_i\) 表示 \(\mathrm{substr}(i)\) 在哪些串中出现过，以状压形式存储，直接在 \(\mathrm{link}\) 树上合并一波即可。

V. P3346 [ZJOI2015]诸神眷顾的幻想乡

由于叶子结点仅有 \(20\) 个，因此从每个叶子结点开始，整棵树都会形成一个字典树。将这 \(20\) 棵 Trie 树拼在一起求 GSAM 就做完了。

VI. P3181 [HAOI2016]找相同字符

建出两个串的 GSAM，设 \(ed_{1, i}\) 表示状态 \(i\) 关于 \(s_1\) 的 \(\mathrm{endpos}\) 集合大小，\(ed_{2,i}\) 同理，答案显然为 \(\sum ed_{1, i}\times ed_{2, i}\times (\mathrm{len}(i) - \mathrm{len}(\mathrm{link}(i)))\)。

VII. P5341 [TJOI2019]甲苯先生和大中锋的字符串

SAM 裸题：建出 \(s\) 的 SAM 后方便得到所有出现 \(k\) 次的子串状态。每个符合题意的状态的子串长度是一段区间，因此差分即可。时间复杂度线性。

VIII. P4341 [BJWC2010]外星联络

SAM 的转移函数刻画了一个字符串 \(s\) 的所有子串，因此直接在该 DAG 上贪心遍历即可。贪心指优先走字符小的出边。

2.9. 相关链接与资料

OI wiki：后缀自动机（SAM）。
hihoCoder：后缀自动机一。
hihoCoder：后缀自动机二。
。
洛谷题单：SA & SAM。
辰星凌：题解 P6139 【模板】广义后缀自动机（广义SAM）。

笔记纸糊船