catpad (catpad) wrote,
catpad
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).
Память, конечно, будет расходоваться чудовищно.

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

Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 8 comments