2

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

正如维基所说：

一组字符串的最长公共子串可以通过为字符串构建一个广义后缀树，然后从它下面的子树中的所有字符串中找到具有叶节点的最深内部节点来找到

正如贾斯汀所说：

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$

在（紧凑）后缀树中，您需要从所有字符串中找到具有叶节点的最深内部节点。如果在同一深度有多个节点，则必须比较该节点表示的字符串的长度。即ABC、BC、C都有相同的深度，所以要比较ABC、BC、C字符串的长度，看哪个更长；这显然是ABC。

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

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

4

2 回答 2

3

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

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

于 2014-09-23T19:14:53.900 回答
0

trie 用于字典。它不存储后缀。

于 2014-09-23T18:20:55.320 回答