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

Question

正如维基所说：

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

正如贾斯汀所说：

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$

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

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

Answer 1

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

Answer 2

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

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