string - 如何高效地在字符串集合中找到指定长度的相同子串？

Question

我有一个集合 S，通常包含 10-50 个长字符串。出于说明目的，假设每个字符串的长度在 1000 到 10000 个字符之间。

我想找到指定长度 k(通常在 5 到 20 的范围内)的字符串，它们是 S 中每个字符串的子字符串。这显然可以使用一种简单的方法来完成 - 枚举 S[0] 中的每个 k 长度子字符串并检查它们是否存在于 S 的每个其他元素中。

有没有更有效的方法来解决这个问题？据我所知，这与最长公共(public)子序列问题有一些相似之处，但我对 LCS 的理解是有限的，我不确定它如何适应我们将所需公共(public)子串长度绑定(bind)到的情况k，或者子序列技术是否可以应用于查找子串。

Answer 1

这是一个相当简单的算法，应该相当快。

1. 使用 rolling hash如 Rabin-Karp string search algorithm , 构造哈希表 H<sub>0</sub>所有的 |S<sub>0</sub>|-k+1长度 k S<sub>0</sub> 的子串.这大约是 O(|S<sub>0</sub>|)因为每个散列都是根据前一个散列在 O(1) 中计算的，但是如果存在冲突或重复子字符串，则需要更长的时间。使用更好的散列将帮助您解决冲突，但如果有很多 k -S<sub>0</sub> 中的长度重复子串那么你最终可能会使用 O(k|S<sub>0</sub>|) .

2. 现在在 S<sub>1</sub> 上使用相同的滚动哈希.这一次，查找 H<sub>0</sub> 中的每个子串如果找到它，请将其从 H<sub>0</sub> 中删除并将其插入新表 H<sub>1</sub> .同样，这应该在 O(|S<sub>1</sub>|) 左右。除非你有一些病理情况，就像S<sub>0</sub>和 S<sub>1</sub>只是同一字符的长重复。 (如果 S<sub>0</sub> 和 S<sub>0</sub> 是相同的字符串，或者有很多重叠部分，它也将是次优的。)

3. 对每个 S<sub>i</sub> 重复第 2 步，每次创建一个新的哈希表。 (在步骤 2 的每次迭代结束时，您可以删除上一步的哈希表。)

最后，最后一个哈希表将包含所有常见的k -length 子字符串。

总运行时间应该约为 O(Σ|S<sub>i</sub>|)但在最坏的情况下可能是O(kΣ|S<sub>i</sub>|) .即便如此，根据描述的问题大小，它应该在可接受的时间内运行。