1. 概述
在本篇文章中，我们将介绍广义后缀树（Generalized Suffix Tree）的概念，并通过一个实际应用案例来展示它如何用于查找两个字符串的最长公共子串（Longest Common Substring）。
广义后缀树是多个字符串的共享后缀结构，它将多个字符串的后缀统一组织成一棵树结构，使得我们可以高效地进行字符串匹配、公共子串查找、子串频率分析等任务。
我们将会：
- 构建一个后缀 Trie
- 优化为 Patricia Trie
- 构建后缀树
- 扩展为广义后缀树
- 应用它来查找最长公共子串
2. 后缀 Trie
后缀 Trie 是构建后缀树的第一步。它本质上是一个多叉树结构，每个边（edge）都标记着字符串中的字符。从根节点出发的路径代表一个完整的后缀。
举个例子，假设我们要构建字符串 nonsense 的后缀 Trie。这个字符串有 9 个后缀（包括空后缀 $）：
- $
- e
- se
- nse
- ense
- sense
- nsense
- onsense
- nonsense
我们依次将这些后缀插入 Trie 中。初始时，根节点只有一个空边。每插入一个新后缀时，如果已有路径匹配前缀，则继续往下走；否则创建新分支。
构建完成后，我们得到一个树结构，每个叶子节点对应一个后缀。图示如下：
继续插入其他后缀，构建完整 Trie：
可以看到，随着插入的进行，很多节点只有一条子路径，这种节点在后续优化中会被压缩。
3. Patricia Trie
Patricia Trie（也叫 Radix Trie） 是对 Trie 的压缩优化。它的核心思想是：
✅ 将连续的、只有一个子节点的节点合并为一条边，从而减少节点数量。
这样做的好处是大大减少了树的节点数，提升了空间和时间效率。
以 nonsense 为例，压缩后的 Patricia Trie 如下图所示：
可以看到，节点数明显减少，但叶子节点数保持不变（仍为 9 个后缀）。
4. 后缀树
后缀树（Suffix Tree） 是基于 Patricia Trie 构建的，每个叶子节点被标注为该后缀在原字符串中的起始索引。
以 nonsense 为例，其后缀树如下：
每个叶子节点标注了该后缀在原字符串中的起始位置。这为我们后续查找子串提供了基础。
5. 广义后缀树
广义后缀树是多个字符串的后缀树的合并版本。它允许我们对多个字符串进行统一的子串查找。
例如，我们有两个字符串：
T1 = nonsenseT2 = offense
我们构建它们的广义后缀树，每个叶子节点标注为 (字符串编号:起始位置)。
构建结果如下图所示：
可以看到，两个字符串的后缀共享了部分路径。这为我们查找它们的公共子串提供了基础。
6. 查找最长公共子串
算法思路：
- 构建两个字符串的广义后缀树；
- 对每个内部节点标注是否包含来自两个字符串的后缀；
- 使用深度优先搜索（DFS）找到深度最大的、包含两个字符串后缀的节点；
- 该节点对应的路径即为最长公共子串。
以 nonsense 和 offense 为例，我们标注每个节点是否来自两个字符串：
通过 DFS，我们找到红色节点，对应路径 ense，即为最长公共子串。绿色节点对应较短的公共子串 nse 和 se。
7. 总结
✅ 广义后缀树是一种高效的数据结构，适用于多字符串的子串查找、相似性分析等任务。
✅ 它的构建过程包括：
- 构建后缀 Trie
- 压缩为 Patricia Trie
- 添加后缀索引
- 扩展为广义结构
✅ 应用场景包括：
- 最长公共子串查找
- 子串频率统计
- 多字符串模式匹配
- 基因组比对等生物信息学任务
⚠️ 虽然构建广义后缀树的算法复杂度较高，但已有多种优化方案，例如在线构建算法（Online Construction）等。
如果你希望快速实现广义后缀树，可以参考一些开源实现：
关键词总结：
- 后缀 Trie ✅
- Patricia Trie ✅
- 后缀树 ✅
- 广义后缀树 ✅
- 最长公共子串 ✅
- 深度优先搜索 ✅
- 子串匹配 ✅
如你所见，广义后缀树是一个强大而优雅的字符串处理工具，虽然实现复杂，但一旦掌握，将极大提升你在字符串处理领域的效率和深度理解。