Изменения

'''Дерево палиндромов''' (англ. ''palindromic tree'') {{---}} структура данных, позволяющая решить некоторые интересные задачи на палиндромы.  Эту структуру данных придумал [http://codeforces.com/profile/MikhailRubinchik Михаил Рубинчик] и рассказал ее на летних сборах в Петрозаводске в 2014 году.

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

Ребра [[Файл:palindrome_tree_nodes.png|Пример четырех вершин дерева палиндромов ориентированные и помечены символами. Ребро с символом <tex>x</tex> из вершины <tex>u</tex> в вершину <tex>v</tex> означает, что <tex>v.value=x+u.value+x</tex>. Тут <tex>``+"</tex> означает конкатенацию строк|border]] [[Файл:palindrome_tree_edge.png|В данном примере мы получаем палиндром aba добавлением символа a к обоим сторонам палиндрома b|border]]

Также в дереве палиндромов присутствуют ''суффиксные ссылки''Стоит обратить внимание на то, что название структуры данных выбрано не совсем удачно. Суффиксная ссылка На самом деле структура представляет из вершины <tex>u</tex> ведет в вершину <tex>w</tex>себя два дерева {{---}} одно для палиндромов чётной длины, если другое для палиндромов нечётной длины. Обозначим корни этих деревьев за <tex>w.valueroot_{even}</tex> является наибольшим суффиксом строки и <tex>u.valueroot_{odd}</tex>соответственно.[[Файл:palindrome_tree_suffix_link.png|Мы добавили суффиксную ссылку (пунктирная линия) из aba к a потому, что a является наибольшим паллиндромом-суффиксом строки aba|border]]

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

<tex>root_{odd}</tex> будет соответствовать фиктивному палиндрому длины При реализации в целях экономии памяти мы не будем хранить для каждой вершины соответствующую ей строку-1палиндром. Это нужно для того, чтобы не обрабатывать отдельно случай добавления палиндрома длины 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>.

{| 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|border500px]] |- |style="background-color:#FFF;padding:2px 30px"|Будем также поддерживать максимальный палиндром-суффикс обработанного префикса <tex>p</tex>. Назовем его <tex>t</tex>. |style="background-color:#FFF;padding:2px 30px"|[[Файл:palindromic_tree_nodes.png|500px]] |- |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]] |}

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

Т.к. Таким образом, чтобы обработать очередной символ <tex>x</tex>, нужно просто спуститься по суффиксным ссылкам вершины <tex>t</tex> находится в уже обработанной части строкидо тех пор, пока мы не найдем подходящую строку <tex>A</tex> (причем мы всегда можем найти такую строку, то ему соответствует какаявозможно длины <tex>-то вершина 1</tex>, если очередная суффиксная ссылка будет вести в деревекорень). У этой Затем нужно проверить, есть ли уже ребро по символу <tex>x</tex> из вершины есть суффиксная ссылка на какую-то другую вершину, у которой тоже есть суффиксная ссылка соответствующей <tex>A</tex>, и т.десли нет, добавить это ребро в новую вершину <tex>xAx</tex>.

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

[[Файл:palindrome_tree_build4{{Утверждение|author=2|statement=Очередная добавленная вершина <tex>u</tex> не может быть максимальным палиндромом-суффиксом какой-либо ранее добавленной вершины <tex>v</tex>|proof=Предположим, что это не так. Тогда оказывается, что не все подпалиндромы строки <tex>v'</tex> были добавлены в дерево палиндромов ранее.png|border]]А это противоречит утверждению 1.}}

Строка <tex>xAx</tex> {{---}} это единственная подстрока-палиндром строки <tex>p+x</tex>, которой, возможно, нет в <tex>p</tex> (все другие подстроки-палиндромы есть). Чтобы понять почему это так, нужно обратить внимание на то, что все новые подстроки-палиндромы, которых не было в <tex>p</tex>, должны оканчиваться на символ <tex>x</tex>, и поэтому должны быть палиндромом-суффиксом строки <tex>p+x</tex>. Из-за того, что <tex>xAx</tex> {{---}} наибольший палиндром-суффикс строки <tex>p+x</tex>, все остальные меньшие палиндромы-суффиксы этой строки уже есть в каком-то префиксе строки <tex>xAx</tex> (т.к. для каждого суффикса палиндрома есть равный ему префикс) и, соответственно, уже есть в <tex>p</tex>. Таким образом, чтобы обработать очередной символ <tex>x</tex>, нужно просто спуститься по суффиксным ссылкам строки <tex>t</tex> до тех пор, пока мы не найдем подходящую строку <tex>A</tex> (причем мы всегда можем найти такую строку, возможно длины -1, если очередная суффиксная ссылка будет вести в корень). Затем нужно проверить, есть ли уже ребро по символу <tex>x</tex> из вершины, соответствующей <tex>A</tex>, и если нет, добавить это ребро в новую вершину <tex>xAx</tex>. Теперь нужно добавить суффиксную ссылку из вершины <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> (т.к. при добавлении очередного символа появляется не более одного нового палиндрома).

Чтобы оценить временную сложность алгоритма, давайте посмотрим что происходит, когда мы строим дерево палиндромов. Можно нужно заметить, что по мере того, как мы обрабатываем строку символ за символом, левая граница наибольшего палиндрома-суффикса уже обработанной строки сдвигается только вправо. Очевидно, эта граница может двигаться вправо не более <tex>n</tex>, где <tex>n</tex> {{---}} длина строки, для которой мы строим дерево. То же самое относится и к левой границе той строки, на которую ведет суффиксная ссылка вновь добавленной вершины.

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

Мы знаемТакже данную структуру можно использовать для подсчета числа различных подпалиндромов строки. Это будет просто число вершин. === Число подпалиндромов ==={{Задача|definition=Требуется определить число подпалиндромов, которые содержатся в данной строке.}} Например, строка <tex>aba</tex> имеет четыре подпалиндрома: дважды <tex>a</tex>, что количество новых подпалиндромов при добавлении символа - это <tex>0b</tex> или и <tex>1aba</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]