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

[catpad]

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


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

voda
eric
nec

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

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

Comments

[voldemar.livejournal.com]

Следующий вариант вырисовывается.

Предварительно по множеству строк строим "дерево чтения строк". Построение начинается с помечнного пустым символом корня дерева. К нему добавляются дочерние вершины, помеченные первыми буквами строк данного множества. Затем к каждой из этих вершин - дочерние вершины, помеченные вторыми буквами слов, начинающихся с соответствующей буквы. И так далее. Таким образом, продвигаясь вглубь по ветвям дерева мы будем читать слова данного множества.

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

Далее нам понадобится множество для хранения указателей на текущие анализируемые вершины дерева. Изначально оно пусто.

Теперь для каждого символа из "входной строки" выполняем:

1. для каждого указателя из множества проверить, есть ли среди дочерних вершин одна, помеченная текущим символом "входной строки"
1. если такая дочерняя вершина есть - переставляем указатель на нее. Если вершина к тому же является листом - алгоритм закончен, мы нашли подстроку
2. если такой дочерней вершины нет - удаляем указатель из множества
2. если среди дочерних вершин корня дерева имеется одна, помеченная текущим символом "входной строки" поместим указатель на нее во множество указателей

(фактически указатель на вершину дерева будет нам говорить о том, что мы смогли начиная с некоторой позиции "входной строки" прочитать последовательность букв, ведущую от корня "дерева строк" к указанной вершине дерева)

Если мы проанализировали все символы "входной строки", значит ни одна из заданного множества строк не является подстрокой "входной строки".

Чтобы оценить трудозатраты алгоритма, заметим, что для каждого символа "входной строки" мы должны проверить каждый указатель вершины из множества. Значит нам нужно оценить верхнюю границу мощности множества указателей на текущие вершины "дерева чтения строк". Поскольку на каждом шаге :

1. мы можем добавить ко множеству указателей один единственный указатель (на текущую букву "входной строки" в корне "дерева чтения строк")
2. каждый ранее введенный указатель продвигается на один уровень вглубь "дерева чтения" или исчезает (в случае если нет соответствующих букв для продвижения)

то максимально возможная мощность множества указателей равна глубине дерева. Итого, в худшем случае нам придется выполнить N*M операций проверки-перемещения указателей. Где N - длина "входной строки", а M - глубина "дерева чтения", или максимальная длина строки из заданного множества.

[catpad.livejournal.com]

Всё верно!
Ну вот, вы тоже изобрели trie, поздравляю! :)

[voldemar.livejournal.com]

Спасибо за термин, запомню на будущее

[green-fr.livejournal.com]

Вова, это офигительно напоминает алгоритм расшифровки морзянки :-)
И - как следствие - архивирование (за названием к Кнуту), где дерево строится так, что наиболее частые символы висят ближе к корню, т.е. кодируются меньшим количеством бит. Только у твоего дерева алфавит больше.

[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]

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