为什么我们不使用前缀树（trie）来查找最长的公共子字符串？

最近我正在学习如何使用树来解决最长的公共子串问题。在从Wiki和其他在线资源中学习之后，我发现我们应该使用后缀树来查找最长的公共子字符串。为什么我们不使用前缀树（trie）来查找最长的公共子字符串？

如维基说：

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

子树作为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$

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

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

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

来源

2014-09-23 JoJo

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

所以你想将所有字符串的所有元素添加到树中实际上是正确的，但与带有后缀树的解决方案相比效率低下。

来源

2014-09-23 19:14:53 kraskevich

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

来源

2014-09-23 18:20:55 Bytemain

但是我们可以用所有字符串的所有后缀建立一个trie，对吧？这是否意味着具有所有后缀的所有字符串都像后缀树一样？ – JoJo 2014-09-23 18:31:53

让我澄清一下：您可以在树的一个顶部建立一个后缀树。这是天真的，但工程。 ukkonen算法更快。在典型情况下，不存在后缀：http：//stackoverflow.com/questions/13893950/suffix-tree-and-tries-what-is-the-difference。 – Bytemain 2014-09-23 19:24:48

为什么我们不使用前缀树（trie）来查找最长的公共子字符串？

回答

相关问题