Дерево палиндромов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание структуры)
(Построение)
Строка 28: Строка 28:
  
 
== Построение ==
 
== Построение ==
 +
Будем обрабатывать строку символ за символом. Пусть мы уже обработали некоторый префикс <tex>p</tex> и теперь хотим добавить следующий символ строки, назовем его <tex>x</tex>.
 +
 +
[[Файл:palindrome_tree_build1.png|border]]
 +
Будем также поддерживать максимальный палиндром-суффикс обработанного префикса <tex>p</tex>. Назовем его <tex>t</tex>.
 +
 +
[[Файл:palindrome_tree_nodes.png|border]]
 +
Т.к. <tex>t</tex> находится в уже обработанной части строки, то ему соответствует какая-то вершина в дереве. У этой вершины есть суффиксная ссылка на какую-то другую вершину, у которой тоже есть суффиксная ссылка и т.д.
 +
 +
[[Файл:palindrome_tree_build3.png|Цепочка суффиксных ссылок из t|border]]
  
 
== Реализация ==
 
== Реализация ==

Версия 19:22, 6 июня 2016

Дерево палиндромов — структура данных, позволяющая решить некоторые интересные задачи на палиндромы.

Эту структуру данных придумал Михаил Рубинчик и рассказал ее на летних сборах в Петрозаводске в 2014 году.


Описание структуры

Дерево палиндромов состоит из вершин. Каждая вершина соответствует палиндрому. Через [math]u.value[/math] будем обозначать строку, которой соответствует вершина [math]u[/math]. Пример четырех вершин дерева палиндромов

Ребра дерева палиндромов ориентированные и помечены символами. Ребро с символом [math]x[/math] из вершины [math]u[/math] в вершину [math]v[/math] означает, что [math]v.value=x+u.value+x[/math]. Тут [math]``+"[/math] означает конкатенацию строк.

В данном примере мы получаем палиндром aba добавлением символа a к обоим сторонам палиндрома b

Также в дереве палиндромов присутствуют суффиксные ссылки. Суффиксная ссылка из вершины [math]u[/math] ведет в вершину [math]w[/math], если [math]w.value[/math] является наибольшим суффиксом строки [math]u.value[/math]. Мы добавили суффиксную ссылку (пунктирная линия) из aba к a потому, что a является наибольшим паллиндромом-суффиксом строки aba


Название структуры данных выбрано не совсем удачно, т.к. на самом деле она представляет из себя два дерева, однако суффиксные ссылки могут вести как в то же, так и в другое дерево. Это сделано для удобства реализации. Также в целях экономии памяти мы не будем хранить для каждой вершины соответствующую ей строку-палиндром. Вместо этого мы будем хранить только длину палиндрома.

Итак, у нас будет два дерева. Одно дерево для палиндромов четной длины, другое — для палиндромов нечетной длины. Каждое дерево будет иметь фиктивный корень. Обозначим корни четного и нечетного дерева соответственно [math]root_{even}[/math] и [math]root_{odd}[/math].

[math]root_{odd}[/math] будет соответствовать фиктивному палиндрому длины -1. Это нужно для того, чтобы не обрабатывать отдельно случай добавления палиндрома длины 1. Теперь каждый раз при добавлении новой вершины [math]u[/math] к вершине [math]v[/math] мы будем просто указывать ее длину равной [math]u.len = v.len + 2[/math].

[math]root_{even}[/math] будет соответствовать фиктивному палиндрому длины 0.

Также направим суффиксные ссылки обоих корней к вершине [math]root_{odd}[/math]. Это нужно для того, чтобы [math]/todo[/math].

Построение

Будем обрабатывать строку символ за символом. Пусть мы уже обработали некоторый префикс [math]p[/math] и теперь хотим добавить следующий символ строки, назовем его [math]x[/math].

Palindrome tree build1.png Будем также поддерживать максимальный палиндром-суффикс обработанного префикса [math]p[/math]. Назовем его [math]t[/math].

Palindrome tree nodes.png Т.к. [math]t[/math] находится в уже обработанной части строки, то ему соответствует какая-то вершина в дереве. У этой вершины есть суффиксная ссылка на какую-то другую вершину, у которой тоже есть суффиксная ссылка и т.д.

Цепочка суффиксных ссылок из t

Реализация

Оценка сложности

Применения

Источники