如何使用树找到最长的公共子字符串？

substring algorithm data-structures java tree

2022-09-04 03:35:19

根据wiki，最长的常见子字符串问题可以使用后缀树来解决。
来自维基：

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

我不明白。
示例：如果我有：
，然后
后缀树是（由于空格而省略的一些分支）：ABCDEXABCZXABCZ
enter image description here

最长的常见子字符串是，但不是我看不到wiki的描述如何在这里提供帮助。
不是具有叶节点的最深的内部节点。
任何帮助来理解它是如何工作的？ABCABC

答案 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 中，从所有字符串中找到具有叶节点的最深的内部节点。

希望它有帮助。

答案 2

您实际上尚未绘制后缀树。如果你做得好，在根源上，你只会有一个可能的字符。仅当单个字母可以有多个后续后缀时，树才会拆分。这会在树中强制将公共子字符串组合在一起，从而使它们易于查找。