形态
正如大部分资料所述，是一个 DAG，DAG 上每一条路径都一定和字符串 \(S\) 的一个子串一一对应。
endpos 与等价类
\(\operatorname{endpos}(T)\) 表示子串 \(T\) 在 \(S\) 中右端点结束位置，这里把 \(\operatorname{endpos}(T) = \operatorname{endpos}(T')\) 的 \(T,T'\) 称为一个等价类。
这里可以注意到一些等价类的性质，体现了后缀之间的包含关系。
- 性质一：对于同一个等价类，较短的子串是较长的子串的后缀。
- 性质二：同一个等价类的所有子串长度均不同，且依次递增 \(1\)，覆盖了最短子串到最长子串的区间。
- 性质三：如果一个子串 \(v\) 是另一个子串 \(u\) 的后缀，那么一定有 \(\operatorname{T}(u) \sube \operatorname{T}(v)\)。
- 性质四：一个长度为 \(n\) 的字符串的等价类的数量不超过 \(2n\)。
其中最有用的是性质三，它说明了状态如何转移。
你可以根据性质一、二、三构造出母树，但是这没有什么意义，它并不实用。
后缀自动机的构造
而后缀自动机的巧妙之处正是用路径表达子串。
要想构造后缀自动机，就要知道后缀链。
后缀链
规定一个节点 \(v\) 上最长的一个子串为 \(\operatorname{longest}(v)\)，最短的一个子串为 \(\operatorname{shortest}(v)\)，它们的长度分别为 \(\operatorname{len}(v),\operatorname{minlen}(v)\)。
一个节点 \(v\) 指向之前的一个节点 \(u\)，那么 \(\operatorname{len}(u) + 1 = \operatorname{minlen}(v)\)。
建 SAM
终于步入正题了，前面写得我手麻了。
有如下关键：
1.起点和终点之间的边代表在当前字符串后面加入一个字符。
2.保证从根开始任意一条路径是 \(S\) 的一个子串。
3.每个节点所表示的所有子串都属于一个等价类。
4.点之间关系符合母树的父子关系。
代码如下：
点击查看代码
int idx = -1, lst = 0;
struct node{int pa, son[26], len;
}t[N << 1];void newNode(int lenth){t[++idx].len = lenth, t[idx].pa = -1;memset(t[idx].son, 0, sizeof t[idx].son);
}void ins(int c){newNode(t[lst].len + 1);int p = lst, cur = idx;while(~p && !t[p].son[c])t[p].son[c] = cur, p = t[p].pa; if(p == -1) t[cur].pa = 0;else{int q = t[p].son[c];if(t[q].len == t[p].len + 1) t[cur].pa = q;else{newNode(t[p].len + 1);int nq = idx;memcpy(t[nq].son, t[q].son, sizeof t[q].son);t[nq].pa = t[q].pa;t[q].pa = t[cur].pa = nq;while(q >= 0 && t[p].son[c] == q)t[p].son[c] = nq, p = t[p].pa; }} lst = cur;
}
一些应用
检查字符串是否出现
给一个文本串 \(T\) 和多个模式串 \(P\) ，我们要检查字符串 \(P\) 是否作为 \(T\) 的一个子串出现。
我们在 \(O(\left|T\right|)\) 的时间内对文本串 \(T\) 构造后缀自动机。为了检查模式串 \(P\) 是否在 \(T\) 中出现，我们沿转移（边）从 \(t_0\) 开始根据 \(P\) 的字符进行转移。如果在某个点无法转移下去，则模式串 \(P\) 不是 \(T\) 的一个子串。如果我们能够这样处理完整个字符串 \(P\) ，那么模式串在 \(T\) 中出现过。
对于每个字符串 \(P\) ，算法的时间复杂度为 \(O(\left|P\right|)\) 。此外，这个算法还找到了模式串 \(P\) 在文本串中出现的最大前缀长度。
求不同子串的个数
给一个字符串 \(S\) ，计算不同子串的个数。
构造一个后缀自动机，采用 DP 的思想，从 \([1,n-1]\) 递推到 \([1,n]\) 也就是每加入一个后答案增大，这里记 \(u\) 的后缀链所指向的节点为 \(\operatorname{father}(u)\)，增大了 \(\operatorname{len}(u) - \operatorname{len}(\operatorname{father}(u))\)。
所有不同子串的总长度
给定一个字符串 \(S\) ，计算所有不同子串的总长度。
同样可以利用后缀链接树的信息。每个节点对应的最长子串的所有后缀长度是 \(\frac{\operatorname{len}(𝑣)\times(\operatorname{len}(𝑣)+1)}{2}\)
减去其 \(\operatorname{father}(u)\) 节点的对应值就是该节点的净贡献，对自动机所有节点求和即可。
感觉这里内容比较多，稍后再写吧。
广义后缀自动机
好的，我按照您的要求重新组织标题格式：
广义后缀自动机 vs 普通后缀自动机：核心差异详解
一、核心目的不同
普通后缀自动机：
- 设计目标：处理单个字符串
- 识别：该字符串的所有子串
- 本质：单个字符串所有子串的最小确定性有限状态自动机
广义后缀自动机：
- 设计目标：处理多个字符串
- 识别：所有输入字符串的子串的并集
- 本质：多个字符串子串集合的合并自动机
二、构建过程的关键差异
1. 初始状态重置
- 普通SAM：构建过程连续，
last状态在整个构建过程中持续更新 - 广义SAM：每个新字符串插入时，必须将
last重置为初始状态(0)，否则会错误地将不同字符串连接起来
2. 转移边处理
- 普通SAM：对于当前状态
p和字符c，如果t[p].son[c]不存在，总是创建新状态 - 广义SAM：需要特殊处理已存在的转移：
- 如果
t[p].son[c]已存在且合法，可能复用现有状态 - 这是为了避免为不同字符串的相同前缀重复创建状态
- 如果
3. 克隆策略调整
- 普通SAM中，克隆节点时只需考虑当前字符串
- 广义SAM中，克隆节点需要合并来自不同字符串的
endpos信息
三、状态信息的扩展
普通SAM状态信息：
struct Node {int len; // 最长可接受子串长度int link; // 后缀链接int son[Σ]; // 转移函数// 可能还有：first_pos, 出现次数等
}
广义SAM状态信息：
struct Node {int len; // 最长可接受子串长度int link; // 后缀链接int son[Σ]; // 转移函数bitset<MAX_STR> str_mask; // 关键：记录来自哪些字符串// 可能还有：在每个字符串中的出现次数等
}
关键区别：广义SAM需要维护每个状态属于哪些字符串的信息。
四、算法复杂度差异
时间复杂度：
- 普通SAM：O(n)，n为单个字符串长度
- 广义SAM：O(∑nᵢ)，但常数更大（需要处理重复转移）
- 广义SAM最坏情况下状态数可能达到2∑nᵢ - 1，与普通SAM相同
空间复杂度：
- 两者都是O(n·Σ)，但广义SAM需要额外的O(k)空间存储每个状态的字符串归属信息（k为字符串数量）
五、功能能力的差异
普通SAM能处理，但需要广义SAM的问题：
- 多字符串最长公共子串：需要知道子串在哪些字符串中出现
- 子串在多字符串中的出现统计：统计每个子串在多少个字符串中出现
- 多字符串去重子串查询：查询某个子串是否在任意输入字符串中出现过
只有广义SAM能直接处理：
- 多字符串子串集合的并集操作
- 基于多个字符串的自动补全
- 多文档字符串搜索
六、实现细节差异
拓扑排序的差异：
- 普通SAM：按len排序后，在parent树上DP通常从后往前
- 广义SAM：还需要在DP过程中合并来自不同字符串的统计信息
查询操作的差异：
- 普通SAM查询子串是否出现：直接沿转移边走
- 广义SAM查询子串在哪些字符串中出现：走完转移边后，还要查看状态的
str_mask
七、特殊情况的处理
字符串包含关系：
如果字符串A是字符串B的前缀，在广义SAM中：
- 普通实现可能为A单独创建状态
- 优化实现会复用B的前缀状态
相同前缀/后缀：
不同字符串的相同前缀/后缀会在广义SAM中共享状态，这是空间优化的关键。
八、应用场景选择指南
选择普通SAM当：
- 只处理单个字符串
- 问题只涉及一个文本
- 不需要跨字符串比较
选择广义SAM当：
- 需要同时处理多个字符串
- 需要跨字符串查询子串
- 需要计算多字符串的公共子串
- 需要统计子串在多文本中的分布
九、本质理解
最简单理解：
- 普通SAM = 单个字符串的"所有子串自动机"
- 广义SAM = 多个字符串的"子串并集自动机"
类比：
- 普通SAM像单本书的"索引"
- 广义SAM像多本书的"合并索引"
关键：广义SAM通过共享不同字符串的公共前缀/后缀来节省空间，同时维护每个状态的"来源字符串"信息，从而支持多字符串查询。