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

Question

根据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

您实际上还没有绘制后缀树。如果你做得正确的话，从根本上来说，你只会拥有所有可能的角色一次。仅当单个字母可以有多个后缀时，树才会分裂。这迫使公共子串在树中聚集在一起，从而使它们可以被找到。