Изменения

Эту структуру данных придумал Михаил Рубинчик<ref name="ref1">[http://codeforces.com/profile/MikhailRubinchik Codeforces {{---}} MikhailRubinchik - Codeforces]</ref> и рассказал ее её на летних сборах в Петрозаводске в 2014 году.Наиболее подробное о дереве палиндромов или овердреве (palindromic tree, eertree) можно прочитать в диссертации Михаил Рубинчика [http://www.pdmi.ras.ru/pdmi/dissertatiton/2016-05-25t000000-%D1%80%D1%83%D0%B1%D0%B8%D0%BD%D1%87%D0%B8%D0%BA-%D0%BC%D0%B8%D1%85%D0%B0%D0%B8%D0%BB-%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%B8%D0%BD%D0%BE%D0%B2%D0%B8%D1%87]

[[Дерево ,_эквивалентные_определения|Дерево]] палиндромов состоит из вершин. Каждая вершина , каждая из которых соответствует палиндрому. Все вершины соответствуют разным палиндромам. Через <tex>u'</tex> будем обозначать строку, которой соответствует вершина <tex>u</tex>.Ребра [[Основные_определения_теории_графов#def_graph_edge_1|Рёбра]] дерева палиндромов ориентированные и помечены символами. Ребро с символом <tex>x</tex> ведет из вершины <tex>u</tex> в вершину <tex>v</tex> означаеттогда и только тогда, что когда <tex>v'=xu'x</tex>.

Название структуры данных выбрано не совсем удачно, т[[Файл:palindrome_tree_suffix_link.png|Мы добавили суффиксную ссылку (пунктирная линия) из aba к. на самом деле она представляет из себя два дереваa потому, однако суффиксные ссылки могут вести как в то же, так и в другое дерево. Это сделано для удобства реализации. Также в целях экономии памяти мы не будем хранить для каждой вершины соответствующую ей строкучто a является наибольшим паллиндромом-палиндром. Вместо этого мы будем хранить только длину палиндрома.суффиксом строки aba|border]]

<tex>root_{odd}</tex> будет соответствовать фиктивному палиндрому длины <tex>При реализации в целях экономии памяти мы не будем хранить для каждой вершины соответствующую ей строку-1</tex>палиндром. Это нужно для того, чтобы не обрабатывать отдельно случай добавления палиндрома длины 1Этот подход был бы неэффективным с точки зрения памяти. Теперь каждый раз при добавлении новой вершины <tex>u</tex> к вершине <tex>v</tex> Вместо этого мы будем просто указывать ее хранить только длину равной <tex>u.len = v.len + 2</tex>палиндрома (и для некоторых задач позицию палиндрома в строке).

Итак, структура будет состоять из двух деревьев и, соответственно, двух корней. Для удобства реализации каждый корень будет соответствовать фиктивной строке.* <tex>root_{odd}</tex> будет соответствовать палиндрому длины <tex>-1</tex>. Это нужно для того, чтобы не обрабатывать отдельно случай добавления палиндрома длины <tex>1</tex>. Теперь каждый раз при добавлении ребра из вершины <tex>u</tex> к вершине <tex>v</tex>, мы будем просто считать что <tex>|v'|=|u'| + 2</tex>.* <tex>root_{even}</tex> будет соответствовать фиктивному палиндрому длины <tex>0</tex>.

Также направим суффиксные Суффиксные ссылки обоих корней будут вести к вершине <tex>root_{odd}</tex>. Это соглашение нужно также для удобства реализации {{---}} теперь каждая вершина имеет суффиксную ссылку.

Будем обрабатывать строку символ за символомОпишем далее по шагам процесс построения дерева палиндромов для данной строки. Пусть мы уже обработали некоторый префикс <tex>p</tex> и теперь хотим добавить следующий символ Изначально оно состоит из двух фиктивных вершин, а далее будет достраиваться инкрементально после каждого рассмотренного символа строки, назовем его <tex>x</tex>. [[Файл:palindrome_tree_build1.png|border]] Будем также поддерживать максимальный палиндром-суффикс обработанного префикса <tex>p</tex>. Назовем его <tex>t</tex>.

{| style="background-color:#CCC;margin:0.5px" |- |style="background-color:#FFF;padding:2px 30px"|Будем обрабатывать строку символ за символом. Пусть мы уже обработали некоторый префикс <tex>p</tex> и теперь хотим добавить следующий символ строки, назовем его <tex>x</tex>. |style="background-color:#FFF;padding:2px 30px"|[[Файл:palindrome_tree_build1.png|500px]] |- |style="background-color:#FFF;padding:2px 30px"|Будем также поддерживать максимальный палиндром-суффикс обработанного префикса <tex>p</tex>. Назовем его <tex>t</tex>. |style="background-color:#FFF;padding:2px 30px"|[[Файл:palindromic_tree_nodes.png|border500px]] |- |style="background-color:#FFF;padding:2px 30px"|Т.к. <tex>t</tex> находится в уже обработанной части строки, то ему соответствует какая-то вершина в дереве. У этой вершины есть суффиксная ссылка на какую-то другую вершину, у которой тоже есть суффиксная ссылка и т.д. |style="background-color:#FFF;padding:2px 30px"|[[Файл:palindrome_tree_build3.png|500px|Цепочка суффиксных ссылок из t]] |- |style="background-color:#FFF;padding:2px 30px"|Найдем теперь палиндром-суффикс строки <tex>px</tex> (т.е. нового префикса). Искомая строка будет иметь вид <tex>xAx</tex>, где <tex>A</tex> {{---}} какая-то строка, возможно пустая (или фиктивная строка длины <tex>-1</tex>, соответствующая корню <tex>root_{odd}</tex>, если искомый палиндром-суффикс {{---}} это просто символ <tex>x</tex>). Т.к. <tex>xAx</tex> {{---}} палиндром, то <tex>A</tex> {{---}} тоже палиндром, и, более того, это суффикс строки <tex>p</tex>. Поэтому он может быть достигнут из <tex>t</tex> по суффиксным ссылкам. |style="background-color:#FFF;padding:2px 30px"|[[Файл:palindrome_tree_build4.png|500px]] |}

[[Файл:palindrome_tree_build3{{Утверждение|author=1|statement=Строка <tex>xAx</tex> {{---}} это единственная подстрока-палиндром строки <tex>px</tex>, которой, возможно, нет в <tex>p</tex> (т.pngе. все другие подстроки-палиндромы есть). |Цепочка суффиксных ссылок из t|border]]proof= Заметим, что все новые подстроки-палиндромы, которых не было в <tex>p</tex>, должны оканчиваться на символ <tex>x</tex>, и поэтому должны быть палиндромом-суффиксом строки <tex>px</tex>. Из-за того, что <tex>xAx</tex> {{---}} наибольший палиндром-суффикс строки <tex>px</tex>, все остальные меньшие палиндромы-суффиксы этой строки уже есть в каком-то префиксе строки <tex>xAx</tex> (т.к. для каждого суффикса палиндрома есть равный ему префикс) и, соответственно, уже есть в <tex>p</tex>.}}

Найдем теперь палиндром-суффикс нового префиксаТаким образом, состоящего из <tex>p</tex> и чтобы обработать очередной символ <tex>x</tex>. Искомый палиндром-суффикс будет иметь вид , нужно просто спуститься по суффиксным ссылкам вершины <tex>xAxt</tex>до тех пор, где пока мы не найдем подходящую строку <tex>A</tex> {{---}} какая-то строка(причем мы всегда можем найти такую строку, возможно пустая (или фиктивный строка длины <tex>-1</tex>, соответствующая корню <tex>root_{odd}</tex>, если искомый палиндром-суффикс {{---}} это просто символ <tex>x</tex>очередная суффиксная ссылка будет вести в корень). Т.к. Затем нужно проверить, есть ли уже ребро по символу <tex>xAxx</tex> палиндромиз вершины, то соответствующей <tex>A</tex> {{---}} тоже палиндром, иесли нет, более того, добавить это суффикс строки ребро в новую вершину <tex>pxAx</tex>. Поэтому он может быть достигнут из <tex>t</tex> по суффиксным ссылкам.

[[Файл:palindrome_tree_build4Теперь нужно добавить суффиксную ссылку из вершины <tex>xAx</tex>. Если эта вершина уже существовала до добавления символа <tex>x</tex>, ничего делать не нужно {{---}} суффиксная ссылка и так указывает на правильную вершину. Иначе нужно найти наибольший палиндром-суффикс строки <tex>xAx</tex>, который будет иметь вид <tex>xBx</tex>, где <tex>B</tex> {{---}} это некоторая строка, возможно, пустая. Следуя той же логике, которую мы использовали раньше, <tex>B</tex> {{---}} это палиндром-суффикс строки <tex>p</tex> и может быть достигнут из <tex>t</tex> по суффиксным ссылкам.png|border]]

Таким образом, чтобы обработать очередной символ {{Утверждение|author=2|statement=Очередная добавленная вершина <tex>xu</tex>, нужно просто спуститься по суффиксным ссылкам строки не может быть максимальным палиндромом-суффиксом какой-либо ранее добавленной вершины <tex>tv</tex> до тех пор|proof=Предположим, пока мы что это не найдем подходящую строку <tex>A</tex> (причем мы всегда можем найти такую строкутак. Тогда оказывается, возможно длины что не все подпалиндромы строки <tex>-1v'</tex>, если очередная суффиксная ссылка будет вести были добавлены в корень)дерево палиндромов ранее. Затем нужно проверить, есть ли уже ребро по символу <tex>x</tex> из вершины, соответствующей <tex>A</tex>, и если нет, добавить А это ребро в новую вершину <tex>xAx</tex>противоречит утверждению 1.}}

Теперь нужно добавить суффиксную ссылку из вершины <tex>xAx</tex>. Если эта вершина уже существовала до добавления Таким образом, добавление очередного символа <tex>x</tex>, ничего делать не нужно {{---}} суффиксная ссылка итак указывает на правильную вершину. Иначе на нужно найти наибольший палиндром-суффикс строки <tex>xAx</tex>, который будет иметь вид <tex>xBx</tex>, где <tex>B</tex> {{---}} это некоторая строка, возможно, пустая. Следуя той же логике, которую мы использовали раньше, <tex>B</tex> {{---}} это палиндром-суффикс строки <tex>p</tex> и может быть достигнут из <tex>t</tex> по суффиксным ссылкамописанному алгоритму происходит корректно.

Каждая вершина в дереве соответствует подпалиндрому, всего палиндромов различных подпалиндромов в строке не более <tex>n</tex> (т.к. при добавлении очередного символа появляется не более одного нового палиндрома).

== Реализация Применения ==Рассмотрим пример реализации дерева === Число новых палиндромов. Будем считать, что каждая вершина имеет номер. Свободный для очередной вершины номер будем хранить порождаемых очередным символом ==={{Задача|definition=Необходимо определить число подпалиндромов, которые будут новыми после добавления символа <tex>x</tex> в переменной конец строки <tex>szs</tex>.}}

Для каждой вершины будем хранить длину палиндромаНапример, суффиксную ссылку и массив ребер. В реализации им будут соответствовать массивы <tex>len[\mathrm{MAXN}]</tex>, <tex>suff\_link[\mathrm{MAXN}]</tex> и при добавлении символа <tex>to[\mathrm{MAXN}][\mathrm{ALPHABET\_SIZE}]a</tex> соответственно. Также будем хранить саму строку и длину ее обработанной части к строке <tex>naba</tex>. В переменной <tex>last</tex> будем хранить последнюю добавленную вершину.  '''int''' s[MAXN], len[MAXN], suff_link[MAXN], to[MAXN][ALPHABET_SIZE]; '''int''' n, sz, last; В самом начале нужно инициализировать структуру.   '''void''' init() { n = 0; link[0] = 1; len[1] = -1; sz = 2; } Вспомогательная функция, которая спускается начиная с вершины уже состоит из палиндромов <tex>va</tex> по суффиксным ссылкам до тех пор, пока не придет в палиндром-суффикс <tex>xAxb</tex>. Тут и <tex>xaba</tex> {{---}} последний добавленный символ, а добавляется новый палиндром <tex>Aaa</tex> {{---}} некоторый палиндром.

'''int''' get_sufflink('''int''' v) Мы знаем, что число новых подпалиндромов при добавлении символа <tex>0</tex> или <tex>1</tex>. Так что решение задачи довольно простое {{ '''while''' (s[n - len[v] - 2] != s[n - 1]}} будем строить дерево палиндромов символ за символом и для каждого нового символа отвечать, был ли добавлен новый палиндром или нет (определить это можно, например, по тому, были ли добавлены новые вершины к структуре) v = suff_link[v]; '''return''' v; }.

Чтобы построить дерево палиндромов=== Число подпалиндромов ==={{Задача|definition=Требуется определить число подпалиндромов, нужно просто для каждого символа исходной строки последовательно вызвать <tex>\mathrm{add\_letterкоторые содержатся в данной строке.}}</tex>.

== Применения ===== Количество новых палиндромов, порождаемых очередным символом ===В данной задаче нужно уметь отвечать на вопрос <tex>``</tex>как много новых палиндромов-подстрок появится у строки <tex>s</tex>, если к ней в конец добавить символ <tex>x"</tex>.Например, при добавлении символа <tex>a</tex> к строке строка <tex>aba</tex>, которая уже состоит из палиндромов имеет четыре подпалиндрома: дважды <tex>a</tex>, <tex>b</tex> и <tex>aba</tex>, добавляется новый палиндром <tex>aa</tex>.

Мы знаем, что количество новых подпалиндромов при добавлении символа - это <tex>0</tex> или <tex>1</tex>. Так что решение Для решения задачи довольно простое - будем строить дерево палиндромов символ за символом для данной строки и для каждого нового символа отвечатьна каждом шаге добавлять к ответу все палиндромы, был ли добавлен которые содержат этот новый палиндром или нет (определить это можно, например, по тому, были ли добавлены новые вершины к структуре)символ.

=== Количество подпалиндромов ===В данной задаче нужно уметь отвечать на вопрос Рассмотрим очередной шаг алгоритма после добавления символа <tex>``x</tex> как много подпалиндромов имеет данная строка . Обозначим за <tex>"t</tex>вершину, соответствующую максимальному палиндрому-суффиксу, содержащую этот последний символ. НапримерЗаметим, что новые палиндромы, строка которые добавляет <tex>abax</tex> имеет четыре подпалиндрома: дважды {{---}} это <tex>at'</tex>, а также все палиндромы, достижимые из <tex>bt</tex> и по суффиксным ссылкам (т.к. только они содержат новый символ <tex>x</tex>). Для того чтобы быстро найти их число, будем хранить в каждой вершине длину цепочки суффиксных ссылок до корня (включая саму вершину), а затем будем просто прибавлять к ответу это число для каждого очередного <tex>abat</tex>по мере добавления новых символов.

=== Количество Число вхождений каждого подпалиндрома в строку ===В этой задаче необходимо {{Задача|definition=Необходимо найти количество число вхождений каждого подпалиндрома строкив неё саму.}}

Для каждой вершины <tex>u</tex> дерева палиндромов будем хранить число вхождений строки <tex>u.num'</tex> {{---}} количество вхождений соответствующего вершине палиндрома в исходную строку (не обязательно актуальные данные) и число <tex>u.toAdd</tex>, которое необходимо добавить к <tex>v.num</tex> числу вхождений всех потомков <tex>v</tex> вершины <tex>u</tex>. Назовем такую операцию добавления ''операцией релаксации''. После того, как релаксация будет выполнена для всех предков вершины <tex>u</tex>, можно будет считать, что <tex>u.num</tex> содержит актуальные данныепосчитанное число вхождений соответствует действительности.  

{{Задача|definition=Для данной строки необходимо найти палиндром, произведение длины которого на количество вхождений в строку является максимальным.}} Для решения данной задачи применим тот же алгоритм, что и в прошлой задаче, а затем пройдем по всем вершинам дерева палиндромов и выберем подходящую.

Для решения данной задачи применим тот же алгоритм, что и в прошлой задаче, затем пройдем по всем вершинам дерева палиндромов и выберем подходящую== См.также ==* [[Алгоритм Манакера]]* [[Сжатое суффиксное дерево]]* [[Суффиксный массив]]

==Примечания==

== Источники информации ==* [http://adilet.org/blog/25-09-14/ Adilet.org {{---}} Palindromic tree, Adilet ADJA Zhaxybay]