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

[catpad]

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


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

voda
eric
nec

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

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

Comments

[pigglet.livejournal.com]

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