10

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

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

4

1 回答 1

1

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

  • 找到位置 0 叶L。
  • 如果L有多个同级，则删除从L的父级指向L的指针
  • 如果L恰好有一个兄弟姐妹，则将指针从L的祖父母更改为L的父母，使其指向L的兄弟姐妹。

@jogojapan 进一步建议您保留指向树中最深叶子的指针。这样做有两个问题：L不一定是树中最深的叶子，如Wikipedia 的示例所示，其次，如果您希望能够输出与收到的相同类型的数据结构，一旦删除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) 时间。
于 2013-09-23T23:14:02.463 回答