string - 找到一组等长字符串的重叠部分？

Question

有 100 万个等长字符串（短字符串）。例如

abcdefghi

fghixyzyz

吉阿布卡布克

zyzdddxfg

. . .

我想找到两个字符串的成对重叠。A“abcdefghi”和B“fghixyzyz”的重叠是“fghi”，这是A的最大后缀，B的最大前缀，满足后缀和前缀是平等的。

是否有有效的算法可以找到集合中任意两个字符串的重叠？

Answer 1

一种有效的方法是为字符串集构建一个通用的后缀树。要查找字符串 x 和 y 之间的重叠：

遵循通用后缀树中字符串 y 的路径标签。这条路径上与字符串 x 的终端符号相关的最深节点有一个路径标签，它相当于后缀-前缀重叠 x->y。

有关更多详细信息，请参阅 Gusfield 的书“字符串、树和序列的算法”的第 137 页（“在线性时间内解决所有对后缀前缀问题”）。

注意：如果您的数据集很大（数百万/十亿个字符串），这会占用大量内存。