Дерево палиндромов — различия между версиями
(→Построение) |
(→Построение) |
||
Строка 31: | Строка 31: | ||
[[Файл:palindrome_tree_build1.png|border]] | [[Файл:palindrome_tree_build1.png|border]] | ||
+ | |||
Будем также поддерживать максимальный палиндром-суффикс обработанного префикса <tex>p</tex>. Назовем его <tex>t</tex>. | Будем также поддерживать максимальный палиндром-суффикс обработанного префикса <tex>p</tex>. Назовем его <tex>t</tex>. | ||
[[Файл:palindrome_tree_nodes.png|border]] | [[Файл:palindrome_tree_nodes.png|border]] | ||
+ | |||
Т.к. <tex>t</tex> находится в уже обработанной части строки, то ему соответствует какая-то вершина в дереве. У этой вершины есть суффиксная ссылка на какую-то другую вершину, у которой тоже есть суффиксная ссылка и т.д. | Т.к. <tex>t</tex> находится в уже обработанной части строки, то ему соответствует какая-то вершина в дереве. У этой вершины есть суффиксная ссылка на какую-то другую вершину, у которой тоже есть суффиксная ссылка и т.д. | ||
Версия 19:22, 6 июня 2016
Дерево палиндромов — структура данных, позволяющая решить некоторые интересные задачи на палиндромы.
Эту структуру данных придумал Михаил Рубинчик и рассказал ее на летних сборах в Петрозаводске в 2014 году.
Содержание
Описание структуры
Дерево палиндромов состоит из вершин. Каждая вершина соответствует палиндрому. Через
Ребра дерева палиндромов ориентированные и помечены символами. Ребро с символом
из вершины в вершину означает, что . Тут означает конкатенацию строк.Также в дереве палиндромов присутствуют суффиксные ссылки. Суффиксная ссылка из вершины
Название структуры данных выбрано не совсем удачно, т.к. на самом деле она представляет из себя два дерева, однако суффиксные ссылки могут вести как в то же, так и в другое дерево. Это сделано для удобства реализации. Также в целях экономии памяти мы не будем хранить для каждой вершины соответствующую ей строку-палиндром. Вместо этого мы будем хранить только длину палиндрома.
Итак, у нас будет два дерева. Одно дерево для палиндромов четной длины, другое — для палиндромов нечетной длины. Каждое дерево будет иметь фиктивный корень. Обозначим корни четного и нечетного дерева соответственно
и .будет соответствовать фиктивному палиндрому длины -1. Это нужно для того, чтобы не обрабатывать отдельно случай добавления палиндрома длины 1. Теперь каждый раз при добавлении новой вершины к вершине мы будем просто указывать ее длину равной .
будет соответствовать фиктивному палиндрому длины 0.
Также направим суффиксные ссылки обоих корней к вершине
. Это нужно для того, чтобы .Построение
Будем обрабатывать строку символ за символом. Пусть мы уже обработали некоторый префикс
и теперь хотим добавить следующий символ строки, назовем его .Будем также поддерживать максимальный палиндром-суффикс обработанного префикса
. Назовем его .Т.к.
находится в уже обработанной части строки, то ему соответствует какая-то вершина в дереве. У этой вершины есть суффиксная ссылка на какую-то другую вершину, у которой тоже есть суффиксная ссылка и т.д.