Алгоритмическая задача

[catpad]

Задача пришла из жизни. Это не просто упражнение, а совершенно реальная задача, которую мне необходимо решить на работе. Я её решил, но, может быть, кто-то придумает лучше.


Дано множество строк, например:

voda
eric
nec

и так далее - размер множества любой.
На входе алгоритм получает произвольную строку, например: "vodafone.com".
Как наиболее быстрым способом определить, что эта строка содержит в качестве подстроки (substring) одну из данного множества ?
(В приведённом примере ответ положительный, потому что "voda" - это подстрока "vodafone.com").

Задача простая, но ключевые слова здесь, конечно - "наиболее быстро".
Я придумал как это сделать почти за линейное время. "Почти" в смысле, что я не очень хорошо помню, что такое "amortized complexity", но, кажется, получается как раз O(n).
Завтра опубликую ответ, но хотелось бы посмотреть на разные предложения.

Comments

[motya.livejournal.com]

Примерно так:

Препроцессинг: хэщируем строки, таким образом, доступ к нужной строке будет О(1).
Определяем множество (это может быть связный список, это не важно) кандидатов, в котором будут сидеть строки (или их инжекс в хэше) и для каждой строки еще поле "проверено до Х буквы". Сейчас это множество пусто.

Для каждой буквы из инпута проделываем следущее: для каждого кандидата из множества сравниваем букву из инпута с Х+1 (где Х - "проверено до ... буквы") буквой кандидата. Если эти буквы разные, выкидываем кандидата из списка, если одинаковые инкрементируем его "проверено до ... буквы". Далее, берем из хэша все слова начинающиеся на эту букву (ту, что считали из инпута) и добавляем в список кандидатов, устанавливая "проверено до ... буквы" в 1.

Алгоритм останавливается, если "проверено до ... буквы" для некоторого кандидата будет равно количеству букв в нем. В этом случае ответом будет этот самый кандидат. Если такового не нашлось, а инпут кончился - значит не судьба...

В нормальном случае сложность такого алгоритма О(длина инпута).

[motya.livejournal.com]

Дополнение: ключ хэша - буквы (первая, затем, если слишком много на какой-нибудь букве сидит, то там сабхэш по второй букве и т.д.).
Понятно, что одна и та же строка может быть в списке кандидатов несколько раз с разным "проверено до ... буквы".