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

[catpad]

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


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

voda
eric
nec

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

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

Comments

[voldemar.livejournal.com]

В архивировании trie (спасибо catpad'у за термин - запомню) может использоваться для все того же - поиска подстрочек, например внутри алгоритма LZW (http://algolist.manual.ru/compress/standard/lzw.php). Но в tire не наблюдается никакой связи удаленности узлов от корня с частотой появления (частотой появления где?) помечающего этот узел символа не наблюдается. Уже хотя бы потому что одним и тем же символом могут быть помечены несколько вершин: в trie важна только последовательность чтения символов.
Но главное, ты, по-моему запутался в двух алфавитах :-) У Хаффмана (http://algolist.manual.ru/compress/standard/huffman.php), про которого ты судя по всему и вспомнил, есть два алфавита: кодируемый {a..z} (то что ты называешь символами, "висящими ближе к корню") и кодирующий {0,1} (то что ты называешь "алфавитом"). Да, в результате алгоритма построения бинарного словаря по Хаффману получается trie для кодирующего алфавита {0, 1}. Фактически, мы получаем частный случай trie - бинарное дерево. А символами кодируемого алфавита {a-z} помечаются только листья. Тогда, читая закодированный (сжатый поток) посимвольно (побитно) и перемещаясь по trie (бинарному дереву), мы сможем прочесть закодированное сообщение в алфавите {a..z}, если будем запоминать последовательность посещенных листьев. А тот факт, что мы строим trie таким специальным образом, что чаше встречающиеся символы кодируемого алфавита подвешены на конце более коротких "веточек", позволяет нам закодировать исходное сообщение в алфавите {a..z} более компактным образом в алфавите {0,1}.

[green-fr.livejournal.com]

Точно, Хаффман.
Я разницу вижу, я просто и сходство заметил :-)