如何反转字符串的后缀树（findind它表示的字符串）

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

我们将字符串中的所有字符划分为等价类。

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

归纳假设：假设我们已经将长度为k的后缀的所有字符恰当地分成了等价类。 我们也可以对长度为k + 1的后缀进行适当的处​​理。

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

当所有角色被划分为等价类时，我们只需要为每个类指定一个唯一的符号（如果我们需要保持一个正确的字典顺序，我们可以检查其中哪一个更早出现。为此，我们需要查看从根开始的边的顺序）。

时间复杂度是O(n ^ 3) （有n足够的，我们遍历O(n)其他每个足够的他们，我们计算他们的lca在O(n) （我假设我们在这里使用朴素算法） ）。 到现在为止还挺好。

现在让我们用几个观察来得到一个线性解决方案：

我们并不需要这个lca。 我们只需要检查它不是根。 因此，我们可以根据它们的祖先，将所有叶子划分为等价类，这些祖先是根的直接子。 它可以使用深度优先搜索以线性时间完成。 两个足够的最长公共前缀是非空的，如果它们在同一个类中。

我们实际上并不需要检查所有短的足够。 我们只需要检查距离左边和右边最近的一个搜索顺序。 从给定的左边到右边找到最接近的较小数字是一个标准问题，它有一个线性解决方案和一个堆栈。

就是这样：我们至多检查给定的一个，每个检查是O(1) 。 我们现在有一个线性解决方案。