Эффективная структура данных для поиска подстроки?

Предположим, у меня есть набор строк 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 нужно сначала обработать в какую-то умную структуру данных, потому что я буду запрашивать каждый S с большим количеством строк q, поэтому амортизированная стоимость этой предварительной обработки может быть разумной.

РЕДАКТИРОВАТЬ: Чтобы уточнить, мне все равно, , какой член S является подстрокой q, важно, является ли хотя бы один из них. Другими словами, меня интересует только логический ответ.