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

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

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

最佳答案

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

查找位置为0的叶子L.

如果L有多个同级，请删除L的父代到L的指针

如果L具有正好一个同级，请将指针从L的祖 parent 更改为L的父级，以便指向L的同级。

@jogojapan进一步建议您保持指向树中最深叶的指针。这样做有两个问题:L不一定是树中最深的叶子，如Wikipedia's example shows；第二，如果您希望能够输出与接收到的相同类型的数据结构，则一旦删除L，您需要找到新的位置为0的叶子，这将需要O(m)的时间。

(您可以做的是在O(m)时间内构造一个指向每个叶子的指针的数组，并在另一个O(m)时间内按位置对它们进行计数排序。然后，您就可以构造所有树{S [t ..n]:1
假设您对摊销时间不感兴趣，让我们证明您提出的要求是不可能的。

我们知道任何修改S [1..m]后缀树的算法都必须从根开始:它不能从其他任何地方开始，因为我们对底层的具体数据结构一无所知，而且我们也不知道树的节点具有父指针，因此可从中访问整棵树的唯一位置是根。

我们还知道，它必须先定位位置0的叶子，然后才能希望将数据结构修改为S [2..m]的后缀树。为此，它显然必须遍历根与position-0叶子之间的每个节点。

问题是，考虑a ^ m(字符重复m次)的后缀树:路径的长度为m-1。因此，任何算法都必须至少访问m-1个节点，因此在最坏的情况下花费O(m)时间。

关于algorithm - 从字符串S [1..m]的后缀树生成字符串S [2..m]的后缀树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16407600/