string - 为什么我们不使用前缀树 (trie) 来查找最长公共(public)子串？

Question

最近在学习如何用树来解决最长公共(public)子串问题。在引用了Wiki和其他在线资源后，我发现我们应该使用后缀树来查找最长公共(public)子串。

正如维基所说:

The longest common substrings of a set of strings can be found by building a generalised suffix tree for the strings, and then finding the deepest internal nodes which have leaf nodes from all the strings in the subtree below it

作为Justin说:

String = ABCDE$XABCZ$
    End of word character 1 = $
    └── (0)
        ├── (20) $
        ├── (22) ABC
        │   ├── (15) DE$
        │   └── (23) Z$
        ├── (24) BC
        │   ├── (16) DE$
        │   └── (25) Z$
        ├── (26) C
        │   ├── (17) DE$
        │   └── (27) Z$
        ├── (18) DE$
        ├── (19) E$
        ├── (21) XABCZ$
        └── (28) Z$

In a (compact) suffix tree, you need to find the deepest internal node(s) which have leaf nodes from all the strings. If you have multiple nodes at the same depth, you have to compare the length of the string represented by that node. i.e. ABC, BC, and C all have the same depth, so you have to compare the length of ABC, BC, and C strings to see which is longer; which is ABC obviously.

这里我认为从所有字符串中寻找具有叶节点的最深内部节点的过程实际上是从所有字符串中寻找所有后缀的最长公共(public)前缀的过程。

所以这里有一个问题:为什么我们不构建前缀树来存储所有字符串的所有后缀？然后我们可以搜索前缀树来找到这些后缀的最长公共(public)前缀。我分不清这两者之间的区别。谁能给我一些线索，为什么我们使用后缀树而不是前缀树来解决这个问题？

Answer 1

对于长度为N 的字符串，后缀树只需要O(N) 的时间和空间。这就是为什么使用它可以在线性时间内解决最长公共(public)子串问题的原因。 在最坏的情况下，将字符串的所有后缀添加到 trie 需要 O(N^2) 时间和空间。

因此，您将所有字符串的所有后缀添加到一个 trie 中的想法实际上是正确的，但与使用后缀树的解决方案相比效率较低。