string - 如何反转字符串的后缀树(找到它代表的字符串)

Question

给定一棵(修改过的/损坏的)后缀树，它在每条边上存储当前子串的开头和结尾，但不存储子串本身，即看起来像这样的后缀树:

这棵树表示字母表中的字符串“banana”:{a, b, n}。

我正在寻找的算法是找到那种树代表的字符串，对于上面的例子，我希望算法找到“banana”。我想在复杂度为 O(|string|) 的地方 |string|是正在搜索的字符串的长度。可以假设:

字母表的大小是恒定的，每个字符串都从索引 1 开始。

Answer 1

1. 让我们从一些多项式时间解决方案开始:

   • 让我们将字符串中的所有字符分成等价类。

   • 我们已经知道:这是一个特殊的 $符号。

   • 归纳假设:假设我们已经正确划分了长度为k的后缀的所有字符。进入等价类。对于长度为k + 1的后缀我们可以适当的做，也是。

   • 证明:让我们迭代所有长度足够的 i <- 1...k并检查长度为k的后缀的最长公共(public)前缀的长度和长度的后缀 i不为零。它是非零的当且仅当相应叶子的最低共同祖先不是树的根。如果我们找到了这样的后缀，我们就知道它的第一个字母等于当前后缀的第一个字母。所以我们可以加上长度后缀的第一个字母k + 1到适当的等价类。否则，它属于自己的等价类。

   • 当所有的字符都被划分为等价类时，我们只需要为每个类分配一个唯一的符号(如果我们需要保持正确的字典顺序，我们可以检查哪个更早。这样做，我们需要查看从根开始的边的顺序)。

   • 时间复杂度为O(n ^ 3) (有 n 就足够了，我们迭代 O(n) 对它们中的每一个都满足其他条件，然后我们在 O(n) 中计算它们的 lca(我假设我们在这里使用了一个朴素的算法))。到目前为止，一切顺利。

2. 现在让我们使用多个观察来获得线性解决方案:

   • 我们真的不需要 lca。我们只需要检查它不是根。因此，我们可以根据它们的祖先(根的直接子节点)将所有叶子划分为等价类。它可以使用深度优先搜索在线性时间内完成。当且仅当它们属于同一类时，两个后缀的最长公共(public)前缀是非空的。

   • 我们实际上不需要检查所有较短的后缀。我们只需要在深度优先搜索顺序中检查最接近左侧和右侧的一个。从给定的左边和右边找到最接近的较小数字是一个标准问题，它有一个带堆栈的线性解决方案。

   • 就是这样:对于给定的，我们最多检查另外两个满足条件，每个检查都是 O(1) .我们现在有一个线性解决方案。

此解决方案假设这样的字符串确实存在。如果这个假设不可行，我们可以使用这个算法构造一些​​字符串，然后使用 Ukkonnen 算法为其线性构建一个后缀树，并检查它是否与给定的完全相同。