如何使用树找到最长的常见子串？

根据wiki的最长公共子串问题可以使用后缀树来解决。
来自维基 ：

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

我不懂。
示例：如果我有：
ABCDE和XABCZ
那么后缀树是（由于空格而省略了XABCZ一些分支）：

最长的公共子字符串是ABC但我不知道wiki的描述在这里有什么帮助。
ABC不是具有叶节点的最深的内部节点。
任何帮助，以了解这是如何工作的？

Answer 1

就像之前所说的那样，你的树是不正确的。

这是我通过代码运行“ABCDE $ XABCZ”时得到的结果。

后缀树代码 ：

 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。

后缀Trie代码 ：

 └── null ├── A │ └── B │ └── C │ ├── D │ │ └── (E) ABCDE │ └── (Z) ABCZ ├── B │ └── C │ ├── D │ │ └── (E) BCDE │ └── (Z) BCZ ├── C │ ├── D │ │ └── (E) CDE │ └── (Z) CZ ├── D │ └── (E) DE ├── (E) E ├── X │ └── A │ └── B │ └── C │ └── (Z) XABCZ └── (Z) Z 

在（非紧凑）后缀trie中，找到所有字符串中具有叶节点的最深内部节点。

希望能帮助到你。

Answer 2

您实际上没有绘制后缀树。 如果你做得恰当，在根部你只会拥有一次所有可能的角色。 仅当单个字母可以具有多个后续后缀时，树才会分裂。 这迫使树中的公共子串一起使用，这使得它们可以找到。