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

Question

有百万相等长度的字符串（短字符串）。例如

ABCDEFGHI

fghixyzyz

ghiabcabc

zyzdddxfg

的。 。 。

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

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

Answer 1

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

请按照通用后缀树中字符串y的路径标签。沿着这条路径最深的节点是入射到字符串x的终端符号的路径标签，它相当于后缀前缀重叠x-> y。

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

注意：如果数据集很大（百万/十亿字符串），则会使用大量内存。