简述
编辑（03/2019）：我已重新设计了我的实现，使用C++17的string_view来表示我的子字符串，并采用缓存机制确保参考字符串不会移动。更新版本可在github上找到：https://github.com/Rerito/suffix-tree-v2。这是我旧版实现的github (in C++)，供好奇者参考。噢，新版还包括测试！
为了构建广义后缀树，原始算法并不需要进行修改。
详细分析
我的直觉是正确的。为了跟上原始算法中使用的技巧，我们确实需要添加对原始字符串的引用。此外，该算法是在线的，这意味着您可以在树中实时添加字符串。
假设我们有一个字符串(S1, ..., SN)的广义后缀树 GST(N)。现在的问题是如何处理使用GST(N)来构建GST(N+1)的过程。
调整数据模型
在简单情况下（单个后缀树），每个转换都是一对（子字符串，结束顶点）。Ukkonen算法的技巧是使用指向原始字符串中适当位置的一对指针来模拟子字符串。在这里，我们还需要将这样的子字符串链接到其“父”字符串。为此：
- 将原始字符串存储在哈希表中，为它们分配唯一的整数键。
- 现在一个子字符串变成了：(ID, (左指针，右指针))。因此，我们可以使用ID在O(1)时间内获取原始字符串。
我们称之为映射子串。我使用的C++ typedef是我原来问题中的那些。
template <typename C>
class Node {
typedef std::pair<int, int> substring;
typedef std::pair<int, substring> mapped_substring;
typedef std::pair<mapped_substring, Node*> transition;
std::unordered_map<C, transition> g;
Node *suffix_link;
};
你会看到，我们将保留“参考对”这一概念。这次，“参考对”与转换一样，将包含一个“映射子字符串”。
注：与C++中一样，字符串索引从0开始。
插入新字符串
我们希望将SN+1插入到GST(N)中。
GST(N)可能已经有很多节点和转换。在简单的树中，我们只有根和特殊的汇点节点。在这里，我们可能已经通过插入一些先前的字符串添加了SN+1的转换。首先要做的是通过转换向下遍历树，直到匹配SN+1。
这样做，我们最终会到达一个状态r。这个状态可能是显式的（即我们恰好在一个顶点上）或者是隐式的（在转换的中间发生了不匹配）。我们使用与原始算法相同的概念来模拟这样的状态：引用对。以下是一个快速示例：
- 我们想要插入SN+1=
banana
- 表示
ba的节点s在GST(N)中显式地存在
- s有一个转移t，用于子字符串
nal
当我们沿着树向下走时，我们在字符l处到达转移t，这是一个不匹配。因此，我们得到的隐含状态r由引用对(s,m)表示，其中m是映射的子字符串(N+1,(1,3))。
在这里，r是算法第5次迭代的活动点，在构建banana的后缀树时。我们到达该状态的事实恰好意味着bana的树已经在GST(N)中构建好了。
在这个例子中，我们从第5次迭代开始恢复算法，使用
bana的树来构建
banan的后缀树。为了不失一般性，我们将说明
r=
(s, (N+1, (k, i-1))，其中
i是第一个不匹配的索引。确实有
k ≤ i（相等意味着
r是显式状态）。
属性: 我们可以恢复Ukkonen的算法，在迭代i（在SN+1中插入索引为i的字符）时构建GST（N）。这个迭代的活动点是我们通过沿着树向下走得到的状态r。 唯一需要调整的是一些提取操作以解决子字符串。
性质的证明
首先，这种状态 r 的存在意味着中间树的整个状态 T(N+1)i-1 也存在。因此一切都已准备就绪，我们恢复算法。
我们需要证明算法中的每个过程都保持有效。有三个这样的子例程：
test_and_split: 给定要插入的字符，测试是否需要将转换分成两个独立的转换，并确定当前点是否为终点。canonize: 给定一个 参考对 (n, m)，其中 n 是一个顶点，m 是一个映射的子字符串，返回表示相同状态的二元组 (n', m')，使得 m' 是最短可能的子字符串。update: 更新 GST(N)，使其在运行结束时具有中间树 T(N+1)i 的所有状态。
test_and_split
输入：一个顶点 s，一个映射的子串 m = (l, (k, p)) 和一个字符 t。
输出：一个布尔值，表示状态 (s, m) 是否是当前迭代的终点，如果不是则返回一个表示 (s, m) 的节点 r。
最简单的情况首先考虑。如果子串为空（k > p），则状态已经被明确地表示出来。我们只需要测试是否到达了终点。在 GST 中，就像在普通后缀树中一样，每个节点始于给定字符的转移 ALWAYS 最多只有一个。因此，如果有以 t 开始的转移，则返回 true（已到达终点），否则返回 false。
现在是困难的部分，当 k ≤ p 时。我们首先需要获取原始字符串表中索引为 l 的字符串 S
l。
让 (l',(k',p')) (相应地 s') 成为与转换 TR 相关的子字符串（相应地节点），其以字符 S
l(k) 开头。这样的转换存在，因为 (s, (l,(k,p)) 表示中间树 T(N+1)
i-1 上边界路径上的（现有）隐式状态。此外，我们可以肯定这个转换上的前 p - k 个字符匹配。
我们需要拆分这个转移吗？这取决于这个转移的第
Δ = p - k + 1个字符
(**)。为了测试这个字符，我们需要获取哈希表上索引
l'处的字符串，并获取索引
k' + Δ处的字符。这个字符是有保证存在的，因为我们正在检查的状态是隐式的，因此结束在转移
TR的中间
(Δ ≤ p' - k')。
如果相等，则我们无需做任何操作并返回true（终点在此）。否则，我们必须拆分转移并创建一个新状态
r。现在
TR变成了
(l', (k', k' + Δ - 1)) → r。另外一个转移被创建到
r：
(l', (k' + Δ, p')) → s'。现在我们返回false和
r。
(*)：
l不一定等于
N+1。同样，
l和
l'可能不同（或相同）。
(**): 注意，数字 Δ = p - k + 1 完全不取决于所选择的字符串作为映射子字符串。它仅取决于传递给例程的隐式状态。
规范化
输入: 一个节点 _s_ 和一个映射子字符串 (l, (k, p)) 表示树中现有状态 e。
输出: 一个节点 s' 和一个映射子字符串 (l', (k', p')) 表示状态 e 的规范参考。
使用相同的获取技巧，我们只需沿着树向下走，直到我们已经用尽了字符“池”。在这里，就像对于 test_and_split 一样，每个转换的唯一性和我们有一个现有状态作为输入提供了一个有效的过程。
更新
输入: 活动点和当前迭代的索引。
输出: 下一次迭代的活动点。
update使用canonize和test_and_split，它们都是GST-friendly。后缀链接编辑与普通树的相同。唯一需要注意的是，我们将使用SN+1作为参考字符串创建open transitions（即指向节点的转换）。因此，在迭代i时，转换将始终链接到映射的子字符串(N+1,(i,∞))。
最后一步
我们需要“关闭”开放的转换。为此，我们只需遍历它们并编辑∞，用L-1替换它，其中L是SN+1的长度。我们还需要一个标记字符串结尾的哨兵字符。这样，叶子节点将永远保持叶子节点。
结论
额外的获取工作增加了一些O(1)操作，略微增加了复杂度的常数因子。但渐近复杂度显然仍然是与插入字符串的长度线性相关的。因此，从长度为n1,...,nN的字符串(S1,..., SN)构建GST(N)的公式如下：
c(GST(N)) = Σi=1..N ni
std::numeric_limits<int>::max()（在文章中表示无穷大）。 - Reritostd::numeric_limits<int>::max() - 1等等。 - j_random_hacker