后缀自动机 (SAM)学习笔记
1. 前言后缀自动机是一种高效的有穷状态机，用于表示一个字符串的所有可能的后缀子串。与传统的后缀树相比，后缀自动机具有较小的空间复杂度和较快的构建速度。
它就是一个要实现能存下一个串中所有子串的算法，按一般来说应当有个状态，而 SAM 却可以用 O(N) 个状态来表示所有子串，因为它把很多个本质相似的子串映射到了同一个状态上。
<hr>2. 基础概念
a. 状态
[*]定义：状态表示了所有具有相同最长公共前缀的子串。
[*]属性：
[*]len：该状态所代表的子串的最大长度。
[*]link：指向另一个状态的指针，用于表示当前状态与前一状态的关系。
b. 转移边
[*]定义：转移边表示从一个状态到另一个状态的路径，通常由字符触发。
[*]结构：每个状态可以有多个转移边，通过这些边可以到达其他状态。
c. 后缀链
[*]定义：后缀链是一系列状态的连接，用于表示字符串中不同长度的后缀子串之间的关系。
[*]作用：在构建自动机时，后缀链帮助维护最长公共前缀的信息。
<hr>3. 构建后缀自动机
a. 初始化
[*]创建初始状态（init），其 len 为 -1，link 指针指向自身。
[*]当前最后插入的字符所对应的节点为 last。
b. 扩展节点
[*]步骤：
[*]创建新节点：当处理一个新的字符时，首先创建一个新的状态，并将其 len 设置为当前 last 的 len + 1。
[*]回溯检查：从当前 last 开始回溯，沿着转移边和后缀链寻找可以添加新转移边的状态。如果某个状态的子节点已经存
在，则更新 link 指针。
[*]维护最后公共状态：在回溯过程中，确保所有相关状态的后缀链正确。
c. 实现细节
[*]使用C++中的类或结构体来表示状态和转移边：
struct state { int len; int link; unordered_map<char, int> next;// 转移边：字符到状态的映射};<hr>4. 核心算法
a. 延伸节点
[*]函数描述：
[*]给定当前 last 状态和一个新字符 c，创建并返回新的状态。
[*]实现步骤：
[*]初始化新的状态 p，并将 p.len = last->len + 1。
[*]遍历从 last 开始的后缀链，寻找可以添加转移边的状态 q。
[*]更新 q 的子节点，确保不存在冲突。
[*]返回新状态 p 并更新 last。
b. 计算出现次数
[*]方法：
[*]利用后缀自动机的性质，通过遍历所有状态并统计其 len 属性来计算不同子串的出现次数。
[*]代码示例：
int countOccurrences() { int res = 0; for (const auto& state : states) { if (state.len != -1) { res += state.len - state.link; } } return res;}c. 最长公共前缀
[*]方法：
[*]在两个字符串中找到最长的共同前缀。
[*]实现步骤：
[*]将问题转换为在后缀自动机中查找对应的路径。
[*]使用回溯算法从根节点开始，沿着转移边寻找最长公共前缀。
<hr>5. 高级应用
a. 最长回文子串
[*]思路：
[*]利用后缀自动机和一些辅助数据结构（如哈希表和manacher）来记录每个位置的对称信息。
[*]遍历所有可能的中心点，寻找最长的回文。
b. 多模式匹配
[*]方法：
[*]将多个模式字符串合并到同一个后缀自动机中。
[*]使用自动机进行高效的多模式匹配。
<hr>6. 常见问题与调试技巧
a. 内存泄漏
[*]确保每个新创建的状态都被正确释放。
b. 指针错误
[*]仔细检查所有状态的 link 和 next 属性是否初始化正确。
c. 性能优化
[*]使用更高效的数据结构（如跳表或平衡二叉树）替代默认的哈希表。
[*]并行化某些不依赖顺序的计算步骤。
7.更多模型扩展
1.检查字符串是否出现
[*]题面
[*]给一个文本串 s 和多个模式串 t，我们要检查字符串 t 是否作为 s 的一个子串出现。
[*]思路
[*]我们先对 s 构建自动机。为了检查模式串 t 是否在 s 中出现，我们沿转移边从起点开始根据 t 的字符进行转移。如果在某个点无法转移下去，则模式串 t 不是 s 的一个子串。如果我们能够这样处理完整个字符串 t，那么模式串在 s 中出现过。
<hr>2.计算给定的字符串中有多少个不同的子串。
[*]题面
[*]给一个字符串 s，计算不同子串的个数。
[*]思路
[*]对字符串 s 构造后缀自动机。每个 s 的子串都相当于自动机中的一些路径。因此不同子串的个数等于自动机中以 t_0 为起点的不同路径的条数。令 \(d_{v}\) 为从状态 v 开始的路径数量（包括长度为零的路径）。
<hr>3.所有不同子串的总长度
[*]题面
[*]给定一个字符串 s，计算所有不同子串的总长度。
[*]思路
[*]本题做法与上一题类似，只是现在我们需要考虑分两部分进行动态规划：不同子串的数量 \(d_{v}\) 和它们的总长度 \(ret_{v}\)。
<hr>4.字典序第 k 大子串
[*]题面
[*]给定一个字符串 s。多组询问，每组询问给定一个数 k，查询 S 的所有子串中字典序第 k 大的子串。
[*]思路
[*]字典序第 k 大的子串对应于 SAM 中字典序第 k 大的路径，因此在计算每个状态的路径数后，我们可以很容易地从 SAM 的根开始找到第 k 大的路径。
<hr>5.最小循环移位
[*]题面
[*]给定一个字符串 s。找出字典序最小的循环移位。
[*]思路
[*]字符串 S+S 包含字符串 S 的所有循环移位作为子串。所以问题简化为在 S+S 对应的后缀自动机上寻找最小的长度为 \(\left|S\right|\) 的路径，这可以通过平凡的方法做到：我们从初始状态开始，贪心地访问最小的字符即可。
<hr>6.第一次出现的位置
[*]题面
[*]给定一个文本串 t，多组查询。每次查询字符串 s 在字符串 t 中第一次出现的位置（s 的开头位置）。
[*]思路
[*]这种题又朴素的 O(T|t|) 的做法，但是显然过不了。考虑优化：
我们构造一个后缀自动机。我们对 SAM 中的所有状态预处理位置 \(\operatorname{firstpos}\)。即，对每个状态 v 我们想要找到第一次出现这个状态的末端的位置 \(\operatorname{firstpos}\)。换句话说，我们希望先找到每个集合 \(\operatorname{endpos}\) 中的最小的元素（显然我们不能显式地维护所有 \(\operatorname{endpos}\) 集合）。
为了维护 \(\operatorname{firstpos}\) 这些位置，我们将原函数扩展为 sam_extend()。当我们创建新状态 \(\textit{cur}\) 时，我们令：
\[\operatorname{firstpos}(\textit{cur})=\operatorname{len}(\textit{cur})-1\]
当我们将结点 q 复制到 \(\textit{clone}\) 时，我们令：
\[\operatorname{firstpos}(\textit{clone})=\operatorname{firstpos}(q)\]
（因为值的唯一的其它选项 \(\operatorname{firstpos}(\textit{cur})\) 显然太大了）。
那么查询的答案就是 \(\operatorname{firstpos}(t)-\left|s\right|+1\)，其中 t 为对应字符串 s 的状态。
<hr>7.所有出现的位置
[*]题面
[*]问题同上，这一次需要查询文本串 t 中模式串出现的所有位置。
[*]思路
[*]利用后缀自动机的树形结构，遍历子树，一旦发现终点节点就输出。
<hr>8.最短的没有出现的字符串
[*]题面
[*]给定一个字符串 s 和一个特定的字符集，我们要找一个长度最短的没有在 s 中出现过的字符串。
[*]思路
[*]令 \(d_{v}\) 为节点 v 的答案，即，我们已经处理完了子串的一部分，当前在状态 v，想找到不连续的转移需要添加的最小字符数量。计算 \(d_{v}\) 非常简单。如果不存在使用字符集中至少一个字符的转移，则 \(d_{v}=1\)。否则添加一个字符是不够的，我们需要求出所有转移中的最小值
<hr>
页:
[1]