![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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).
Память, конечно, будет расходоваться чудовищно.
В общем, хорошее освежение памяти на практическом материале.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2005-12-02 02:04 am (UTC)Nikogda takim ne zamorachivalsya... Obychno za menya eto DB delaet :)))
Spasibo, Misha, polozhil v kopilku!
no subject
Date: 2005-12-02 02:26 am (UTC)но вот пришло время, когда система перестала справляться с объемом и нужно что-то срочно выдумывать.
Сделал это улучшение - производительность увеличилась в 4 раза.
Звонишь ты слишком много по своему Водафону, вот что :)
no subject
Date: 2005-12-02 06:30 am (UTC)Или этого по условию задачи не нужно?
В любом случае ты большой молодец! Многие программисты давно уже пользуются только CTRL-C и CTRL-V :)
no subject
Date: 2005-12-02 06:40 am (UTC)Да ну какой там молодец. Это же очень простая задача на самом-то деле. Просто, к сожалению, очень редко в реальной жизни приходится применять какие-то интересные структуры данных, вот я и обрадовался.
no subject
Date: 2005-12-02 07:32 am (UTC)no subject
Date: 2005-12-02 08:36 am (UTC)no subject
Date: 2005-12-02 08:43 am (UTC)Vyzdoravlivai!
no subject
Date: 2005-12-02 03:13 pm (UTC)но, разгоряченный, оценил проход по дереву как O(log N),
и, соответственно, сложность всего алгоритма как O(N*log N).
К тому же я вспомнил, что твой алгоритм решает задачу за О(1),
и, схватив полотенце, раздраженно подумал - придумают же эти япошки..