从字符串S [1..m]的后缀树生成字符串S [2..m]的后缀树

Question

是否存在从字符串S [1..m] 的后缀树生成字符串S [2..m]的后缀树的快速(O(1)时间复杂度)方法？

我熟悉Ukkonen的,所以我知道如何从字符串S [1..m]的后缀树制作字符串S [1..m + 1]的快速后缀树,但我不能将该算法用于反向情况.

Answer 1

好吧，正如 @jogojapan 所说，要从 S[1..m] 树中获取 S[2..m] 树，我们需要：

• 找到位置 0 的叶子L。
• 如果L有多个同级，则删除从L的父级到L 的指针
• 如果L仅有一个兄弟姐妹，请将指针从L的祖父母更改为L的父母，以便它指向L的兄弟姐妹。

@jogojapan 进一步建议您保留一个指向树中最深叶子的指针。这有两个问题：L不一定是树中最深的叶子，如维基百科的示例所示，第二，如果您希望能够输出与收到的相同类型的数据结构，一旦删除L ，您需要找到新的位置 0 叶子，无论如何，这将花费 O(m) 时间。

（你可以做的是在 O(m) 时间内构造一个指向每个叶子的指针数组，并在另一个 O(m) 时间内按位置对它们进行计数排序。然后你就可以构造所有树 { S[t ..n] : 1 <= t <= m }以恒定摊销时间各）

假设您对摊销时间不感兴趣，让我们证明您的要求是不可能的。

• 我们知道任何修改 S[1..m] 后缀树的算法都必须从根开始：它不能从其他任何地方开始，因为我们对底层的具体数据结构一无所知，也不知道树的节点具有父指针，因此可以访问整个树的唯一位置是根。
• 我们还知道，它必须先找到位置 0 的叶子，然后才能希望将数据结构修改为 S[2..m] 的后缀树。为此，它显然必须遍历根和位置 0 叶子之间的每个节点。
• 事情是，考虑a^m（字符a重复m次）的后缀树：路径的长度是m-1。因此任何算法都必须访问至少m-1 个节点，因此在最坏的情况下需要 O(m) 时间。