OI-wiki 广义后缀自动机General SAM完全指南字典树上的后缀自动机构造、线性复杂度证明与多字符串应用【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki广义后缀自动机General Suffix Automaton简称 GSAM / exSAM是由刘研绎在 2015 年国家队论文《后缀自动机在字典树上的拓展》中提出的数据结构其核心思想是把后缀自动机SAM直接建立在字典树Trie之上从而在线性时间内解决多个字符串的子串问题。本文以 OI-wiki 的 general-sam.md 为骨架结合仓库内的 参考实现 与 样例数据完整讲解广义后缀自动机的构造流程、与伪广义 SAM的差异、线性复杂度证明以及两类经典应用读者学完后将能够在竞赛与工程中独立写出正确的广义 SAM 代码并解决多串子串统计问题。前置知识广义后缀自动机基于下面两个知识点构建字典树Trie 树后缀自动机SAM请务必对上述两个知识点非常熟悉之后再来阅读本文特别是对后缀自动机中的**后缀链接link**要能有一定的理解——广义 SAM 的构造本质上就是复用后缀链接在字典树各节点之间建立关系。此外文中涉及的字符串记号约定可以参考 字符串约定。引入起源广义后缀自动机是由刘研绎在其 2015 国家队论文《后缀自动机在字典树上的拓展》中提出的结构即将后缀自动机直接建立在字典树上。大部分可以用后缀自动机处理的字符串的问题均可扩展到 Trie 树上。——刘研绎这句话是理解广义 SAM 价值的关键单串 SAM 能做的子串问题不同子串个数、出现次数、最长公共子串等几乎都能迁移到多个字符串的场景而广义 SAM 正是这种迁移的载体。约定字符串个数为 $k$ 个即 $S_1, S_2, S_3 \dots S_k$约定字典树和广义后缀自动机的根节点为 $0$ 号节点字符集大小记作 $\lvert \Sigma \rvert$仓库实现中取CHAR_NUM 30字符通过ch - a映射为下标见 general-sam_1.cpp。概述后缀自动机Suffix Automaton, SAM是用于处理单个字符串的子串问题的强力工具对一个长度为 $n$ 的字符串它的 SAM 最多有 $2n-1$ 个状态和 $3n-4$ 条转移且可以在 $O(n)$ 时间内构造完成详见 sam.md。而广义后缀自动机General Suffix Automaton则是将后缀自动机整合到字典树中用于解决多个字符串的子串问题。它的思想非常朴素多个字符串共享前缀的部分恰好构成一棵字典树如果直接对每个字符串单独建 SAM公共前缀对应的子串信息会被重复统计、浪费空间与时间而把 SAM 建立在字典树上则天然共享了所有字符串的前缀结构。常见的伪广义后缀自动机在深入标准构造之前先看看网络上最常见的两种偷懒写法。它们实现简单且在不少题目中碰巧正确因此流传甚广方法一拼接法——用特殊符号将多个串直接连接成一个大串如 $S_1 # S_2 # \cdots$再对整个大串建立 SAM方法二重复插入法——对每个串重复在同一个SAM 上进行建立每次建立前将last指针置零。方法 1 和方法 2 的实现方式简单而且在面对题目时通常可以达到和广义后缀自动机一样的正确性所以网络上很多人会选择此类写法。例如在后缀自动机一文的多个字符串最长公共子串应用一节中便使用了方法 1见 sam.md。但是无论方法 1 还是方法 2其时间复杂度较为危险方法 1 需要引入特殊分隔符SAM 的规模被放大到 $O(\sum |S_i| k)$ 级别且分隔符破坏了字符集的纯净性后续处理需要额外特判方法 2 中每个字符串都从根开始重新插入若多个字符串共享大量前缀公共前缀对应的状态会被重复遍历与重建导致均摊复杂度退化。从源码结构看仓库在 general-sam.md 中明确提示了这两种写法的风险并指出通常伪广义后缀自动机的平均复杂度等同于广义后缀自动机的最差复杂度面对大量字符串时伪广义后缀自动机的效率远不如标准的广义后缀自动机。构造广义后缀自动机根据原论文的描述应当在多个字符串上先建立字典树然后在字典树的基础上建立广义后缀自动机。整体流程分三步将所有字符串插入到字典树中从字典树的根节点开始进行 BFS记录下遍历顺序以及每个节点的父亲节点将得到的 BFS 序列按照顺序对每个节点在原字典树上进行构建注意不能对len小于当前len的数据进行操作。第一步字典树的使用首先应对多个串创建一棵字典树这不是什么难事在掌握前置知识的前提下可以很快建立完毕。为了统一上下文的代码仓库给出了一个可能的字典树实现对应 general-sam.md 中的代码constexpr int MAXN 2000000; constexpr int CHAR_NUM 30; struct Trie { int next[MAXN][CHAR_NUM]; // 转移 int tot; // 节点总数[0, tot) void init() { tot 1; } int insertTrie(int cur, int c) { if (next[cur][c]) return next[cur][c]; return next[cur][c] tot; } void insert(const string s) { int root 0; for (auto ch : s) root insertTrie(root, ch - a); } };这里我们得到了一棵依赖于next数组建立的字典树。注意insertTrie的设计若转移已经存在即另一个字符串共享了这个前缀直接返回已有节点不新建节点——这正是广义 SAM 能压缩公共前缀信息的基础。在仓库的完整实现 general-sam_1.cpp 中insertTrie与字典树插入被封装进同一个exSAM结构体并额外提供了insert(const char *s, int n)重载以支持字符数组输入。第二步把字典树看作后缀自动机如果我们把这样一棵树直接认为是一个后缀自动机则可以得到如下结论对于节点i其len[i]和它在字典树中的深度相同如果我们对字典树进行拓扑排序可以得到一串根据len不递减的序列BFS 的结果相同。这里需要回忆单串 SAM 的构造方式后缀自动机在建立的过程中可以视为不断地插入len严格递增的值且差值为 $1$每次插入的新状态cur满足len[cur] len[last] 1。所以我们可以把对字典树进行拓扑排序即 BFS后的结果作为一个队列然后按照这个队列的顺序不断地插入到后缀自动机中。这里有一个关键差异需要理解在普通后缀自动机上前一个节点的len是固定值即为last节点的len但在广义后缀自动机中插入的队列是一个不严格递增的数列每个节点的last是已知且固定的——在字典树上它就是自己的父亲节点。由于在字典树中已经建立了一个近似的后缀自动机所以只需要对整个字典树的结构进行一定的处理即可转化为广义后缀自动机按照前面提出的队列顺序对字典树上的每一个节点进行更新操作最终得到广义后缀自动机。对于每个点的更新操作可以稍微修改一下 SAM 中的插入操作来得到。对于整个插入过程需要注意的是由于插入是按照len不递减的顺序进行的在进行clone后的数据复制过程中不可以复制len小于当前len的数据否则会破坏拓扑序的正确性。线性复杂度的证明为什么这种构造是高效的仓库文档给出了完整的论证由于仅处理 BFS 得到的序列可以保证字典树上所有节点仅经过一次对于最坏情况考虑字典树本身节点个数最多的情况即任意两个字符串没有相同的前缀则节点个数为 $\sum_{i1}^{k}|S_i|$即所有字符串的长度之和而后缀自动机的更新操作的复杂度已经在 后缀自动机 中证明为线性。所以可以证明其最坏复杂度为线性$O(\sum_{i1}^{k}|S_i|)$与所有字符串的总长度成正比。反观伪广义 SAM其平均复杂度往往退化为广义 SAM 的最差复杂度这正是标准构造的价值所在。第三步完整实现对 SAM 的插入函数进行少量必要修改即可得到所需函数。仓库文档给出的核心结构如下对应 general-sam.mdstruct GSA { int len[MAXN]; // 节点长度 int link[MAXN]; // 后缀链接link int next[MAXN][CHAR_NUM]; // 转移 int tot; // 节点总数[0, tot) int insertSAM(int last, int c) { int cur next[last][c]; len[cur] len[last] 1; int p link[last]; while (p ! -1) { if (!next[p][c]) next[p][c] cur; else break; p link[p]; } if (p -1) { link[cur] 0; return cur; } int q next[p][c]; if (len[p] 1 len[q]) { link[cur] q; return cur; } int clone tot; for (int i 0; i CHAR_NUM; i) next[clone][i] len[next[q][i]] ! 0 ? next[q][i] : 0; len[clone] len[p] 1; while (p ! -1 next[p][c] q) { next[p][c] clone; p link[p]; } link[clone] link[q]; link[cur] clone; link[q] clone; return cur; } void build() { queuepairint, int q; for (int i 0; i CHAR_NUM; i) if (next[0][i]) q.push({i, 0}); while (!q.empty()) { auto item q.front(); q.pop(); auto last insertSAM(item.second, item.first); for (int i 0; i CHAR_NUM; i) if (next[last][i]) q.push({i, last}); } } };仓库中的完整可运行版本见 general-sam_1.cpp其中main函数的流程为init()→ 循环读入并insert每个字符串 →build()→ 统计答案。需要注意的初始化细节是init()中必须设置link[0] -1虚拟状态这与单串 SAM 完全一致。这段代码有三处与普通 SAM 不同的关键点理解它们才能真正掌握广义 SAM不需要保存last指针由于整个 BFS 的过程得到的顺序中父节点始终在变化所以并不需要保存last指针build()的 BFS 队列中直接以(字符, 父亲节点)二元组为状态。int cur next[last][c]而非int cur tot;这与正常后缀自动机的写法有差异因为我们插入的节点已经在树型结构中完成了字典树阶段已分配好节点编号所以插入时只需要直接获取即可无需再新建节点。clone后的数据拷贝判断next[clone][i] len[next[q][i]] ! 0 ? next[q][i] : 0;与正常后缀自动机的直接赋值next[clone][i] next[q][i];有差异。这样做是为了避免更新len大于当前节点的值——由于数组len当且仅当这个值被 BFS 遍历并插入到后缀自动机后才会被赋值因此len[next[q][i]] ! 0这一判断能保证 clone 只继承已经完成插入的转移目标而把尚未插入len仍为 0的转移置空。build()中 BFS 的细节也值得留意队列初始将根节点 0 的所有非空转移压入next[0][i]随后每处理一个节点last就把last的所有非空转移压入队列。由于字典树上的转移构成了 DAG 结构这一 BFS 天然等价于按len不递减的拓扑序处理所有节点。性质广义后缀自动机保留了后缀自动机的大部分优良性质结构与单串 SAM 一致广义后缀自动机与后缀自动机的结构一致在后缀自动机上的性质绝大部分均可在广义后缀自动机上生效详见 后缀自动机的性质。例如状态数与转移数仍是线性的len[i] - len[link[i]]的计数公式依然成立。注意字典树结构会被破坏当广义后缀自动机建立后通常字典树结构将会被破坏即通常不可以用广义后缀自动机来解决字典树问题。当然也可以选择准备双倍的空间将后缀自动机建立在另外一个空间上这也正是仓库实现中MAXN 2000000取双倍字符串长度的原因之一见 general-sam_1.cpp 的注释。应用一多个字符串中不同子串个数问题给定 $k$ 个字符串 $S_1 \dots S_k$求这些字符串的所有不同子串的总数重复子串只统计一次。解法可以根据后缀自动机的性质得到以点 $i$ 为结束节点的子串个数等于$$ len[i] - len[link[i]] $$所以可以遍历所有的节点求和得到答案。注意这里的核心是多个字符串共享一个自动机因此子串去重是全局性的。仓库中的完整参考代码为 general-sam_1.cpp其答案统计部分如下exSam.init(); for (int i 0; i n; i) { cin s; int len strlen(s); exSam.insert(s, len); } exSam.build(); long long ans 0; for (int i 1; i exSam.tot; i) { ans exSam.len[i] - exSam.len[exSam.link[i]]; } cout ans endl;注意tot从 1 开始计数根节点 0 不参与统计且答案使用long long防止溢出——多个字符串的不同子串总数可能超过int范围。仓库中同时提供了该代码的配套样例数据输入 general-sam_1.in4个字符串aa、ab、bac、caa输出 general-sam_1.ans10。可以手工验证这四个字符串的公共前缀合并后全部不同子串恰为 10 个包括单字符a、b、c以及跨串统计但不重复计入的aa、ab、ba、ac、ca等。这道题对应洛谷 P6139《【模板】广义后缀自动机广义 SAM》也是检验模板正确性的标准题目。应用二多个字符串间的最长公共子串问题给定 $k$ 个字符串求它们的最长公共子串即在每个字符串中都出现的子串中最长的一个。解法我们需要对每个节点建立一个长度为 $k$ 的数组flag若只需要求长度可以仅为标记数组若需要求出此子串的个数则需要改成计数数组计数阶段在字典树插入字符串时对所有经过的节点进行计数保存在当前字符串所在的数组槽位合并阶段按照len递减的顺序遍历所有节点通过后缀链接将当前节点的flag与link指向的节点的flag合并因为子串出现则其后缀必然也出现统计阶段遍历所有的节点找到一个len最大且满足对于所有的 $k$ 个字符串其flag值均为非 $0$ 的节点此节点的len即为答案。仓库中的完整参考代码为 general-sam_2.cpp其中引入了几个关键辅助数据结构int lenSorted[MAXN]; // 按照 len 排序后的数组仅排序 [1, tot) 部分 int sizeC[MAXN][NUM]; // 表示某个字符串的子串个数 int curString; // 字符串实际个数 int lc[MAXN]; // 计数排序使用的辅助空间数组sortLen()使用计数排序按len对节点排序保证后缀链接合并时len递减的拓扑序getSizeLen()则逆序扫描排序后的数组将每个节点的计数沿后缀链接累加到父节点void getSizeLen() { for (int i tot - 2; i 0; --i) for (int j 0; j curString; j) sizeC[link[lenSorted[i]]][j] sizeC[lenSorted[i]][j]; }其中insertTrie在建立字典树的同时维护计数每次经过节点next[cur][c]时执行sizeC[next[cur][c]][curString]表示当前字符串的第curString个在此节点出现一次见 general-sam_2.cpp。最终在main中遍历所有节点检查每个节点的sizeC[i][j]$j$ 遍历所有字符串是否全部非零取满足条件者中len的最大值for (int i 0; i exSam.tot; i) { bool flag true; for (int j 0; j exSam.curString; j) { if (!exSam.sizeC[i][j]) { flag false; break; } } if (flag) ans max(ans, exSam.len[i]); }仓库配套样例数据输入 general-sam_2.in三个字符串alsdfkjfjkdsal、fdjskalajfkdsla、aaaajfaaaa输出 general-sam_2.ans2最长公共子串为al或la等长度为 2 的子串。这道题对应 SPOJ 的 Longest Common Substring IILCS2同时该题在 sam.md 中给出了基于单串 SAM 的另一类解法对最短串建 SAM其余串逐个匹配并沿后缀链接更新两相对照可以更深刻地理解广义 SAM 在结构上直接支持多串的优势。总结广义后缀自动机的本质是把单串 SAM 的线性构造算法移植到字典树上字典树天然共享多串的公共前缀BFS 拓扑序保证了按len不递减的顺序完成全部节点的插入而clone拷贝时对len的判断则保证了广义场景下的正确性。与拼接分隔符和重置 last 重复插入两种伪写法相比标准构造在最坏情况下仍保持 $O(\sum |S_i|)$ 的线性复杂度。本文涉及的核心代码与数据均已包含在当前仓库中读者可以对照阅读与验证算法讲解docs/string/general-sam.md不同子串个数参考实现docs/string/code/general-sam/general-sam_1.cpp 及样例 general-sam_1.in / general-sam_1.ans最长公共子串参考实现docs/string/code/general-sam/general-sam_2.cpp 及样例 general-sam_2.in / general-sam_2.ans前置知识字典树、后缀自动机掌握了广义 SAM 之后单串场景下的大部分 SAM 技巧endpos集合统计、后缀链接树、不同子串计数等都可以平滑迁移到多串场景这也是它在字符串竞赛题中成为高频模板的原因。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 OI-wiki 广义后缀自动机（General SAM）完全指南：字典树上的后缀自动机构造、线性复杂度证明与多字符串应用
OI-wiki 广义后缀自动机General SAM完全指南字典树上的后缀自动机构造、线性复杂度证明与多字符串应用【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki广义后缀自动机General Suffix Automaton简称 GSAM / exSAM是由刘研绎在 2015 年国家队论文《后缀自动机在字典树上的拓展》中提出的数据结构其核心思想是把后缀自动机SAM直接建立在字典树Trie之上从而在线性时间内解决多个字符串的子串问题。本文以 OI-wiki 的 general-sam.md 为骨架结合仓库内的 参考实现 与 样例数据完整讲解广义后缀自动机的构造流程、与伪广义 SAM的差异、线性复杂度证明以及两类经典应用读者学完后将能够在竞赛与工程中独立写出正确的广义 SAM 代码并解决多串子串统计问题。前置知识广义后缀自动机基于下面两个知识点构建字典树Trie 树后缀自动机SAM请务必对上述两个知识点非常熟悉之后再来阅读本文特别是对后缀自动机中的**后缀链接link**要能有一定的理解——广义 SAM 的构造本质上就是复用后缀链接在字典树各节点之间建立关系。此外文中涉及的字符串记号约定可以参考 字符串约定。引入起源广义后缀自动机是由刘研绎在其 2015 国家队论文《后缀自动机在字典树上的拓展》中提出的结构即将后缀自动机直接建立在字典树上。大部分可以用后缀自动机处理的字符串的问题均可扩展到 Trie 树上。——刘研绎这句话是理解广义 SAM 价值的关键单串 SAM 能做的子串问题不同子串个数、出现次数、最长公共子串等几乎都能迁移到多个字符串的场景而广义 SAM 正是这种迁移的载体。约定字符串个数为 $k$ 个即 $S_1, S_2, S_3 \dots S_k$约定字典树和广义后缀自动机的根节点为 $0$ 号节点字符集大小记作 $\lvert \Sigma \rvert$仓库实现中取CHAR_NUM 30字符通过ch - a映射为下标见 general-sam_1.cpp。概述后缀自动机Suffix Automaton, SAM是用于处理单个字符串的子串问题的强力工具对一个长度为 $n$ 的字符串它的 SAM 最多有 $2n-1$ 个状态和 $3n-4$ 条转移且可以在 $O(n)$ 时间内构造完成详见 sam.md。而广义后缀自动机General Suffix Automaton则是将后缀自动机整合到字典树中用于解决多个字符串的子串问题。它的思想非常朴素多个字符串共享前缀的部分恰好构成一棵字典树如果直接对每个字符串单独建 SAM公共前缀对应的子串信息会被重复统计、浪费空间与时间而把 SAM 建立在字典树上则天然共享了所有字符串的前缀结构。常见的伪广义后缀自动机在深入标准构造之前先看看网络上最常见的两种偷懒写法。它们实现简单且在不少题目中碰巧正确因此流传甚广方法一拼接法——用特殊符号将多个串直接连接成一个大串如 $S_1 # S_2 # \cdots$再对整个大串建立 SAM方法二重复插入法——对每个串重复在同一个SAM 上进行建立每次建立前将last指针置零。方法 1 和方法 2 的实现方式简单而且在面对题目时通常可以达到和广义后缀自动机一样的正确性所以网络上很多人会选择此类写法。例如在后缀自动机一文的多个字符串最长公共子串应用一节中便使用了方法 1见 sam.md。但是无论方法 1 还是方法 2其时间复杂度较为危险方法 1 需要引入特殊分隔符SAM 的规模被放大到 $O(\sum |S_i| k)$ 级别且分隔符破坏了字符集的纯净性后续处理需要额外特判方法 2 中每个字符串都从根开始重新插入若多个字符串共享大量前缀公共前缀对应的状态会被重复遍历与重建导致均摊复杂度退化。从源码结构看仓库在 general-sam.md 中明确提示了这两种写法的风险并指出通常伪广义后缀自动机的平均复杂度等同于广义后缀自动机的最差复杂度面对大量字符串时伪广义后缀自动机的效率远不如标准的广义后缀自动机。构造广义后缀自动机根据原论文的描述应当在多个字符串上先建立字典树然后在字典树的基础上建立广义后缀自动机。整体流程分三步将所有字符串插入到字典树中从字典树的根节点开始进行 BFS记录下遍历顺序以及每个节点的父亲节点将得到的 BFS 序列按照顺序对每个节点在原字典树上进行构建注意不能对len小于当前len的数据进行操作。第一步字典树的使用首先应对多个串创建一棵字典树这不是什么难事在掌握前置知识的前提下可以很快建立完毕。为了统一上下文的代码仓库给出了一个可能的字典树实现对应 general-sam.md 中的代码constexpr int MAXN 2000000; constexpr int CHAR_NUM 30; struct Trie { int next[MAXN][CHAR_NUM]; // 转移 int tot; // 节点总数[0, tot) void init() { tot 1; } int insertTrie(int cur, int c) { if (next[cur][c]) return next[cur][c]; return next[cur][c] tot; } void insert(const string s) { int root 0; for (auto ch : s) root insertTrie(root, ch - a); } };这里我们得到了一棵依赖于next数组建立的字典树。注意insertTrie的设计若转移已经存在即另一个字符串共享了这个前缀直接返回已有节点不新建节点——这正是广义 SAM 能压缩公共前缀信息的基础。在仓库的完整实现 general-sam_1.cpp 中insertTrie与字典树插入被封装进同一个exSAM结构体并额外提供了insert(const char *s, int n)重载以支持字符数组输入。第二步把字典树看作后缀自动机如果我们把这样一棵树直接认为是一个后缀自动机则可以得到如下结论对于节点i其len[i]和它在字典树中的深度相同如果我们对字典树进行拓扑排序可以得到一串根据len不递减的序列BFS 的结果相同。这里需要回忆单串 SAM 的构造方式后缀自动机在建立的过程中可以视为不断地插入len严格递增的值且差值为 $1$每次插入的新状态cur满足len[cur] len[last] 1。所以我们可以把对字典树进行拓扑排序即 BFS后的结果作为一个队列然后按照这个队列的顺序不断地插入到后缀自动机中。这里有一个关键差异需要理解在普通后缀自动机上前一个节点的len是固定值即为last节点的len但在广义后缀自动机中插入的队列是一个不严格递增的数列每个节点的last是已知且固定的——在字典树上它就是自己的父亲节点。由于在字典树中已经建立了一个近似的后缀自动机所以只需要对整个字典树的结构进行一定的处理即可转化为广义后缀自动机按照前面提出的队列顺序对字典树上的每一个节点进行更新操作最终得到广义后缀自动机。对于每个点的更新操作可以稍微修改一下 SAM 中的插入操作来得到。对于整个插入过程需要注意的是由于插入是按照len不递减的顺序进行的在进行clone后的数据复制过程中不可以复制len小于当前len的数据否则会破坏拓扑序的正确性。线性复杂度的证明为什么这种构造是高效的仓库文档给出了完整的论证由于仅处理 BFS 得到的序列可以保证字典树上所有节点仅经过一次对于最坏情况考虑字典树本身节点个数最多的情况即任意两个字符串没有相同的前缀则节点个数为 $\sum_{i1}^{k}|S_i|$即所有字符串的长度之和而后缀自动机的更新操作的复杂度已经在 后缀自动机 中证明为线性。所以可以证明其最坏复杂度为线性$O(\sum_{i1}^{k}|S_i|)$与所有字符串的总长度成正比。反观伪广义 SAM其平均复杂度往往退化为广义 SAM 的最差复杂度这正是标准构造的价值所在。第三步完整实现对 SAM 的插入函数进行少量必要修改即可得到所需函数。仓库文档给出的核心结构如下对应 general-sam.mdstruct GSA { int len[MAXN]; // 节点长度 int link[MAXN]; // 后缀链接link int next[MAXN][CHAR_NUM]; // 转移 int tot; // 节点总数[0, tot) int insertSAM(int last, int c) { int cur next[last][c]; len[cur] len[last] 1; int p link[last]; while (p ! -1) { if (!next[p][c]) next[p][c] cur; else break; p link[p]; } if (p -1) { link[cur] 0; return cur; } int q next[p][c]; if (len[p] 1 len[q]) { link[cur] q; return cur; } int clone tot; for (int i 0; i CHAR_NUM; i) next[clone][i] len[next[q][i]] ! 0 ? next[q][i] : 0; len[clone] len[p] 1; while (p ! -1 next[p][c] q) { next[p][c] clone; p link[p]; } link[clone] link[q]; link[cur] clone; link[q] clone; return cur; } void build() { queuepairint, int q; for (int i 0; i CHAR_NUM; i) if (next[0][i]) q.push({i, 0}); while (!q.empty()) { auto item q.front(); q.pop(); auto last insertSAM(item.second, item.first); for (int i 0; i CHAR_NUM; i) if (next[last][i]) q.push({i, last}); } } };仓库中的完整可运行版本见 general-sam_1.cpp其中main函数的流程为init()→ 循环读入并insert每个字符串 →build()→ 统计答案。需要注意的初始化细节是init()中必须设置link[0] -1虚拟状态这与单串 SAM 完全一致。这段代码有三处与普通 SAM 不同的关键点理解它们才能真正掌握广义 SAM不需要保存last指针由于整个 BFS 的过程得到的顺序中父节点始终在变化所以并不需要保存last指针build()的 BFS 队列中直接以(字符, 父亲节点)二元组为状态。int cur next[last][c]而非int cur tot;这与正常后缀自动机的写法有差异因为我们插入的节点已经在树型结构中完成了字典树阶段已分配好节点编号所以插入时只需要直接获取即可无需再新建节点。clone后的数据拷贝判断next[clone][i] len[next[q][i]] ! 0 ? next[q][i] : 0;与正常后缀自动机的直接赋值next[clone][i] next[q][i];有差异。这样做是为了避免更新len大于当前节点的值——由于数组len当且仅当这个值被 BFS 遍历并插入到后缀自动机后才会被赋值因此len[next[q][i]] ! 0这一判断能保证 clone 只继承已经完成插入的转移目标而把尚未插入len仍为 0的转移置空。build()中 BFS 的细节也值得留意队列初始将根节点 0 的所有非空转移压入next[0][i]随后每处理一个节点last就把last的所有非空转移压入队列。由于字典树上的转移构成了 DAG 结构这一 BFS 天然等价于按len不递减的拓扑序处理所有节点。性质广义后缀自动机保留了后缀自动机的大部分优良性质结构与单串 SAM 一致广义后缀自动机与后缀自动机的结构一致在后缀自动机上的性质绝大部分均可在广义后缀自动机上生效详见 后缀自动机的性质。例如状态数与转移数仍是线性的len[i] - len[link[i]]的计数公式依然成立。注意字典树结构会被破坏当广义后缀自动机建立后通常字典树结构将会被破坏即通常不可以用广义后缀自动机来解决字典树问题。当然也可以选择准备双倍的空间将后缀自动机建立在另外一个空间上这也正是仓库实现中MAXN 2000000取双倍字符串长度的原因之一见 general-sam_1.cpp 的注释。应用一多个字符串中不同子串个数问题给定 $k$ 个字符串 $S_1 \dots S_k$求这些字符串的所有不同子串的总数重复子串只统计一次。解法可以根据后缀自动机的性质得到以点 $i$ 为结束节点的子串个数等于$$ len[i] - len[link[i]] $$所以可以遍历所有的节点求和得到答案。注意这里的核心是多个字符串共享一个自动机因此子串去重是全局性的。仓库中的完整参考代码为 general-sam_1.cpp其答案统计部分如下exSam.init(); for (int i 0; i n; i) { cin s; int len strlen(s); exSam.insert(s, len); } exSam.build(); long long ans 0; for (int i 1; i exSam.tot; i) { ans exSam.len[i] - exSam.len[exSam.link[i]]; } cout ans endl;注意tot从 1 开始计数根节点 0 不参与统计且答案使用long long防止溢出——多个字符串的不同子串总数可能超过int范围。仓库中同时提供了该代码的配套样例数据输入 general-sam_1.in4个字符串aa、ab、bac、caa输出 general-sam_1.ans10。可以手工验证这四个字符串的公共前缀合并后全部不同子串恰为 10 个包括单字符a、b、c以及跨串统计但不重复计入的aa、ab、ba、ac、ca等。这道题对应洛谷 P6139《【模板】广义后缀自动机广义 SAM》也是检验模板正确性的标准题目。应用二多个字符串间的最长公共子串问题给定 $k$ 个字符串求它们的最长公共子串即在每个字符串中都出现的子串中最长的一个。解法我们需要对每个节点建立一个长度为 $k$ 的数组flag若只需要求长度可以仅为标记数组若需要求出此子串的个数则需要改成计数数组计数阶段在字典树插入字符串时对所有经过的节点进行计数保存在当前字符串所在的数组槽位合并阶段按照len递减的顺序遍历所有节点通过后缀链接将当前节点的flag与link指向的节点的flag合并因为子串出现则其后缀必然也出现统计阶段遍历所有的节点找到一个len最大且满足对于所有的 $k$ 个字符串其flag值均为非 $0$ 的节点此节点的len即为答案。仓库中的完整参考代码为 general-sam_2.cpp其中引入了几个关键辅助数据结构int lenSorted[MAXN]; // 按照 len 排序后的数组仅排序 [1, tot) 部分 int sizeC[MAXN][NUM]; // 表示某个字符串的子串个数 int curString; // 字符串实际个数 int lc[MAXN]; // 计数排序使用的辅助空间数组sortLen()使用计数排序按len对节点排序保证后缀链接合并时len递减的拓扑序getSizeLen()则逆序扫描排序后的数组将每个节点的计数沿后缀链接累加到父节点void getSizeLen() { for (int i tot - 2; i 0; --i) for (int j 0; j curString; j) sizeC[link[lenSorted[i]]][j] sizeC[lenSorted[i]][j]; }其中insertTrie在建立字典树的同时维护计数每次经过节点next[cur][c]时执行sizeC[next[cur][c]][curString]表示当前字符串的第curString个在此节点出现一次见 general-sam_2.cpp。最终在main中遍历所有节点检查每个节点的sizeC[i][j]$j$ 遍历所有字符串是否全部非零取满足条件者中len的最大值for (int i 0; i exSam.tot; i) { bool flag true; for (int j 0; j exSam.curString; j) { if (!exSam.sizeC[i][j]) { flag false; break; } } if (flag) ans max(ans, exSam.len[i]); }仓库配套样例数据输入 general-sam_2.in三个字符串alsdfkjfjkdsal、fdjskalajfkdsla、aaaajfaaaa输出 general-sam_2.ans2最长公共子串为al或la等长度为 2 的子串。这道题对应 SPOJ 的 Longest Common Substring IILCS2同时该题在 sam.md 中给出了基于单串 SAM 的另一类解法对最短串建 SAM其余串逐个匹配并沿后缀链接更新两相对照可以更深刻地理解广义 SAM 在结构上直接支持多串的优势。总结广义后缀自动机的本质是把单串 SAM 的线性构造算法移植到字典树上字典树天然共享多串的公共前缀BFS 拓扑序保证了按len不递减的顺序完成全部节点的插入而clone拷贝时对len的判断则保证了广义场景下的正确性。与拼接分隔符和重置 last 重复插入两种伪写法相比标准构造在最坏情况下仍保持 $O(\sum |S_i|)$ 的线性复杂度。本文涉及的核心代码与数据均已包含在当前仓库中读者可以对照阅读与验证算法讲解docs/string/general-sam.md不同子串个数参考实现docs/string/code/general-sam/general-sam_1.cpp 及样例 general-sam_1.in / general-sam_1.ans最长公共子串参考实现docs/string/code/general-sam/general-sam_2.cpp 及样例 general-sam_2.in / general-sam_2.ans前置知识字典树、后缀自动机掌握了广义 SAM 之后单串场景下的大部分 SAM 技巧endpos集合统计、后缀链接树、不同子串计数等都可以平滑迁移到多串场景这也是它在字符串竞赛题中成为高频模板的原因。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考