子串搜索的高效数据结构？

Question

假设我有一组字符串S和一个查询字符串q.我想知道S的任何成员是否是q的子串.(出于这个问题的目的,substring包含相等,例如"foo"是"foo"的子串.)例如,假设执行我想要的函数被调用anySubstring:

S = ["foo", "baz"]
q = "foobar"
assert anySubstring(S, q)  # "foo" is a substring of "foobar"

S = ["waldo", "baz"]
assert not anySubstring(S, q)

是否有任何易于实现的算法来实现时间复杂度为子线性len(S)？如果必须首先将S处理成一些聪明的数据结构,这是可以的,因为我将使用大量q字符串查询每个S,因此这种预处理的摊销成本可能是合理的.

编辑:为了澄清,我不关心S的哪个成员是q的子串,只是至少有一个是.换句话说,我只关心布尔答案.

Answer 1

我认为Aho-Corasick算法可以满足您的需求.我认为还有另一个解决方案非常简单,它是Karp-Rabin算法.

Answer 2

因此，如果 S 的长度远小于潜在子字符串的长度总和，那么最好的选择是从 S 构建后缀树，然后在其中进行搜索。这与 S 的长度加上候选子串的总长度成线性关系。当然，不可能有更复杂的算法，因为您至少必须传递所有输入。如果情况相反，即 s 的长度大于子字符串的总长度，则最佳选择是aho-corasick。

希望这可以帮助。