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

[catpad]

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


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

voda
eric
nec

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

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

Comments

[elephantum.livejournal.com]

надо собрать такой здоровый regexp (он же недетерминированый КА)
.*((voda)|(eric)|(nec)).*

откомпилировать в детерминированый КА и за линейное время определить принадлежит ли одно из ключевых слов входному и заодно определить какое.

расходы на компиляцию константные. матчинг по детерминированному КА - линейное время.

подробнее читать - Ахо и Ульмана, либо найти либу по работе с regexp'ами, которая так уже делает.

[potan.livejournal.com]

Констнантные для произвольного регуляра? А если он сравним по объему со всем текстом.
Кроме того, для одной строки известны алгоритмы, которые ищут ее быстрее, чем если ее интерпретировать как регулярное выражение (они заглядывают вперед, и смотрят на сколько символов надо сместиться - получается в константу, зависящую от длины искомой строки, раз быстрее). Эти алгоритмы должны обобщаться и на регулярные выражения, но мне такие не известны.

[elephantum.livejournal.com]

я не говорил про произвольный регуляр. вид регуляра я задал в своем посте. вообще регуляр я вспомнил только потому что NDFSM рисовать лень было.