string - 用于子串搜索的高效数据结构？

Question

假设我有一组字符串 S 和一个查询字符串 q。我想知道 S 的任何成员是否是 q 的子串。 (出于这个问题的目的，子字符串包括相等性，例如“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 的子串，只关心是否至少有一个是。换句话说，我只关心 bool 值答案。

Answer 1

我认为Aho-Corasick algorithm做你想做的事。我认为还有另一种实现起来非常简单的解决方案，它是 Karp-Rabin algorithm .