string - 如何查找所有 3 个字符或更长的公共子字符串

Question

是否有一种有效的算法来搜索和转储 2 个字符串之间的所有常见子字符串（长度为 3 或更长）？

示例输入：

Length   : 0    5    10   15   20   25   30

String 1 : ABC-DEF-GHI-JKL-ABC-ABC-STU-MWX-Y
String 2 : ABC-JKL-MNO-ABC-DEF-PQR-DEF-ZWX-Y

示例输出：

In string 1           2
---------------------------
ABC-DEF   0           12
ABC-DE    0           12
BC-DEF    1           13
:
-ABC-     15,19       11
-JKL-     11          3
-DEF-     3           15
-JKL      11          3
JKL-      12          4
-DEF      3           15,23
DEF-      4           16
WX-Y      29          29
ABC-      0,16,20     0,12
-ABC      15,19       11
DEF-      4           16,24
DEF       4           16,24
ABC       0,16,20     0,12
JKL       12          4
WX-       29          29
X-Y       30          30
-AB       15,19       11
BC-       1,17,21     1,13
-DE       3           15,23
EF-       5           17,25
-JK       11          3
KL-       13          5
:

在示例中，“-D”、“-M”也是一个常见的子字符串，但不是必需的，因为它的长度只有 2。（示例中可能缺少一些输出，因为它们太多了......）

Answer 1

您可以使用称为通用后缀树的数据结构找到所有常见的子字符串

Libstree包含一些用于查找最长公共子字符串的示例代码。可以修改该示例代码以获取所有常见的子字符串。