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

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的子串，只关心是否至少有一个是。换句话说，我只关心布尔型答案。