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

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)

IsЕсть ли простой в реализации алгоритм, чтобы сделать это с временной сложностью, сублинейной в len(S)?Это нормально, если сначала нужно обработать S в какую-нибудь умную структуру данных, потому что я буду запрашивать каждый S с большим количеством строк q, поэтому амортизированная стоимость этой предварительной обработки может быть разумной.

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

Answer 1

Я думаю Алгоритм Aho-Corasick делает то, что вы хотите. Я думаю, что есть другое решение, которое очень просто реализовать, это алгоритм Карпа-Рабина .

Answer 2

Так что, если длина S намного меньше, чем сумма длин потенциальных подстрок, лучшим вариантом будет построить дерево суффиксов из S и затем выполнить поиск в нем.Это линейно по отношению к длине S плюс суммарная длина подстрок-кандидатов.Конечно, не может быть алгоритма с большей сложностью, так как вы должны пройти хотя бы все входные данные.Если случай противоположный, то есть длина s больше, чем общая длина подстрок, ваш лучший вариант будет aho-corasick .

Надеюсь, это поможет.

Answer 3

Создайте регулярное выражение .*(S1|S2|...|Sn).* и создайте его минимальный DFA.

Запустите строку запроса через DFA.