Ответ

[catpad]

Ответ к задаче.


В общем, как мне тут правильно сказали, я изобрёл велосипед и применил к решению задачи структуру под названием trie, сам того не зная.

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



Для примера использованы строки:

vada
veda
voda
xoda
xoxab
xozy
xoxaz

Моё дерево по виду несколько отличается от того, которое приводится в описании trie, но если "подцепить" его за верхнюю букву "v" и посмотреть, что произойдёт под действием гравитации, то станет ясно, что это и есть бинарное (хотя бы по виду) дерево.

Небольшое объяснение:
Первый уровень "дерева" предназначен для первых букв всех данных строк, причём эти буквы расположены в упорядоченном по алфавиту списке. (Так как в нашем примере только две буквы встречаются на первых местах - v,x - то и список состоит из двух элементов.)
Второй уровень предназначен для вторых букв, причём упорядоченные списки из вторых букв прикрепляются к тем буквам, продолжениями которых они являются. (Например, к первой букве v прикреплён список a -> e -> o, потому что эти буквы являются вторыми в словах, начинающихся на v: vada, veda, voda.)
Третий уровень для третьих букв и так далее.

Глубина дерева - это максимальная длина строки из данного множества, обозначим её К.
Длина самого длинного из списков - это число всех возможных символов в данных строках. Число это, очевидно, конечно; обозначим его М.

Поиск по дереву - это проход по упорядоченному списку со спуском на нижний уровень, когда искомая буква найдена. Так будет выглядеть проход по дереву в поисках строки "xoxaz":



Понятно, что сложность прохода = О(К*М) = О(1).

Чтобы определить, есть ли в данном множестве подстрока строки, полученной на входе, нужно просто пройти по всем буквам этой строки и применить к ним алгоритм поиска, что даёт линейную сложность О(K*M*N) = O(N).

Интересно, что поиск можно убыстрить, повесив на буквы не упорядоченные списки, а бинарные деревья поиска. Тогда сложность получится О(K*log(M)*N), что, впрочем, дела не меняет.
Можно пойти ещё дальше и вместо списков и деревьев повесить на буквы массивы, в которых индех будет соответствовать букве, что превращает поиск в молниеносный спуск по дереву всего лишь за К ходов, что опять же не меняет общую сложность алгоритма: О(К*N) = O(N).
Память, конечно, будет расходоваться чудовищно.

В общем, хорошее освежение памяти на практическом материале.

Comments

[barabek.livejournal.com]

Я сегодня за чисткой зубов подумал о подобной структуре,
но, разгоряченный, оценил проход по дереву как O(log N),
и, соответственно, сложность всего алгоритма как O(N*log N).

К тому же я вспомнил, что твой алгоритм решает задачу за О(1),
и, схватив полотенце, раздраженно подумал - придумают же эти япошки..