1
правка
Изменения
м
Таким образом, чтобы обработать очередной символ <tex>x</tex>, нужно просто спуститься по суффиксным ссылкам строки <tex>t</tex> до тех пор, пока мы не найдем подходящую строку <tex>A</tex> (причем мы всегда можем найти такую строку, возможно длины <tex>-1</tex>, если очередная суффиксная ссылка будет вести в корень). Затем нужно проверить, есть ли уже ребро по символу <tex>x</tex> из вершины, соответствующей <tex>A</tex>, и если нет, добавить это ребро в новую вершину <tex>xAx</tex>.
Теперь нужно добавить суффиксную ссылку из вершины <tex>xAx</tex>. Если эта {{Утверждение|author=2|statement=Очередная добавленная вершина уже существовала до добавления символа <tex>xu</tex>, ничего делать не нужно {{может быть максимальным палиндромом-суффиксом какой--}} суффиксная ссылка итак указывает на правильную вершину. Иначе на нужно найти наибольший палиндром-суффикс строки либо ранее добавленной вершины <tex>xAxv</tex>|proof=Предположим, который будет иметь вид <tex>xBx</tex>что это не так. Тогда оказывается, где что не все подпалиндромы строки <tex>Bv'</tex> {{---}} были добавлены в дерево палиндромов ранее. А это некоторая строка, возможно, пустаяпротиворечит утверждению 1. Следуя той же логике, которую мы использовали раньше, <tex>B</tex> {{---}} это палиндром-суффикс строки <tex>p</tex> и может быть достигнут из <tex>t</tex> Таким образом, добавление очередного символа по суффиксным ссылкамописанному алгоритму происходит корректно.
== Реализация ==
Рассмотрим пример реализации дерева палиндромов. Будем считать, что каждая вершина имеет номер. Свободный для очередной вершины номер будем хранить в переменной <tex>sz</tex>.
Для каждой вершины будем хранить длину палиндрома, суффиксную ссылку и массив ребер. В реализации им будут соответствовать массивы <tex>len[\mathrm{MAXN}]</tex>, <tex>suff\_link[\mathrm{MAXN}]</tex> и <tex>to[\mathrm{MAXN}][\mathrm{ALPHABET\_SIZE}]</tex> соответственно. Также будем хранить саму строку и длину ее обработанной части <tex>n</tex>. В переменной <tex>last</tex> будем хранить последнюю добавленную вершину.
'''int''' s[MAXN], len[MAXN], suff_link[MAXN], to[MAXN][ALPHABET_SIZE];
'''int''' n, sz, last;
В самом начале нужно инициализировать структуру.
'''void''' init() {
n = 0;
suff_link[0] = 1;
len[1] = -1;
sz = 2;
}
Вспомогательная функция, которая спускается начиная с вершины <tex>v</tex> по суффиксным ссылкам до тех пор, пока не придет в палиндром-суффикс <tex>xAx</tex>. Тут <tex>x</tex> {{---}} последний добавленный символ, а <tex>A</tex> {{---}} некоторый палиндром.
'''int''' get_sufflink('''int''' v) {
'''while''' (s[n - len[v] - 2] != s[n - 1]) v = suff_link[v];
'''return''' v;
}
И, наконец, процедура добавления очередного символа в структуру:
'''void''' add_letter('''int''' c) {
s[n++] = c;
last = get_sufflink(last);
'''if''' (!to[last][c]) {
len[sz] = len[last] + 2;
link[sz] = to[get_sufflink(suff_link[last])][c];
to[last][c] = sz++;
}
last = to[last][c];
}
Чтобы построить дерево палиндромов, нужно просто для каждого символа исходной строки последовательно вызвать <tex>\mathrm{add\_letter}</tex>.
Уметь отвечать на вопрос Необходимо определить число подпалиндромов, которые будут новыми после добавления символа <tex>``x</tex>как много новых палиндромов-подстрок появится у в конец строки <tex>s</tex>, если к ней в конец добавить символ <tex>x"</tex>.}}
Уметь отвечать на вопрос <tex>``</tex> как много Требуется определить число подпалиндромов имеет данная строка <tex>"</tex>, которые содержатся в данной строке.}}
== Примечания ==
<references/>
Нет описания правки
'''Дерево палиндромов''' (англ. ''palindromic tree'') {{---}} структура данных, позволяющая решить некоторые интересные задачи на палиндромы.
Эту структуру данных придумал Михаил Рубинчик<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_nodes.png|Пример четырех вершин дерева палиндромов|border]] [[Файл:palindrome_tree_edge.png|В данном примере мы получаем палиндром aba добавлением символа a к обоим сторонам палиндрома b|border]]
Стоит обратить внимание на то, что название структуры данных выбрано не совсем удачно. На самом деле структура представляет из себя два дерева {{---}} одно для палиндромов четной чётной длины, другое для палиндромов нечетной нечётной длины. Обозначим корни этих деревьев за <tex>root_{even}</tex> и <tex>root_{odd}</tex> соответственно.
Помимо вершин и ребер рёбер в дереве палиндромов также присутствуют ''суффиксные ссылки''. Для каждой вершины <tex>u</tex> ее её суффиксная ссылка ведет в такую вершину <tex>w</tex>, что <tex>w'</tex> является наибольшим суффиксом строки <tex>u'</tex> относительно других вершин. При этом важно понимать, что суффиксная ссылка из вершины одного дерева может вести как в то же, так и в другое дерево.
[[Файл:palindrome_tree_suffix_link.png|Мы добавили суффиксную ссылку (пунктирная линия) из aba к a потому, что a является наибольшим паллиндромом-суффиксом строки aba|border]]
Итак, структура будет состоять из двух деревьев и, соответственно, двух корней. Для удобства реализации каждый корень будет соответствовать фиктивной строке.
* <tex>root_{odd}</tex> будет соответствовать палиндрому длины <tex>-1</tex>. Это нужно для того, чтобы не обрабатывать отдельно случай добавления палиндрома длины <tex>1</tex>. Теперь каждый раз при добавлении новой ребра из вершины <tex>u</tex> к вершине <tex>v</tex> , мы будем просто указывать ее длину равной считать что <tex>|v'|=|u.len = v.len '| + 2</tex>.* <tex>root_{even}</tex> будет соответствовать фиктивному палиндрому длины <tex>0</tex>.
Суффиксные ссылки обоих корней будут вести к вершине <tex>root_{odd}</tex>. Это соглашение нужно также для удобства реализации {{---}} теперь каждая вершина имеет суффиксную ссылку.
== Построение ==
Опишем далее по шагам процесс построения дерева палиндромов для данной строки. Изначально оно состоит из двух фиктивных вершин, а далее будет достраиваться инкрементально после каждого рассмотренного символа строки. {| borderstyle="1background-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|border]]
|-
|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|border]]
|-
|style="background-color:#FFF;padding:2px 30px"|Т.к. <tex>t</tex> находится в уже обработанной части строки, то ему соответствует какая-то вершина в дереве. У этой вершины есть суффиксная ссылка на какую-то другую вершину, у которой тоже есть суффиксная ссылка и т.д. |style="background-color:#FFF;padding:2px 30px"|[[Файл:palindrome_tree_build3.png|500px|Цепочка суффиксных ссылок из t|border]]
|-
|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|border]]
|}
{{Утверждение
|author=1
|statement=
Строка <tex>xAx</tex> {{---}} это единственная подстрока-палиндром строки <tex>p+xpx</tex>, которой, возможно, нет в <tex>p</tex> (т.е. все другие подстроки-палиндромы есть).
|proof=
Заметим, что все новые подстроки-палиндромы, которых не было в <tex>p</tex>, должны оканчиваться на символ <tex>x</tex>, и поэтому должны быть палиндромом-суффиксом строки <tex>p+xpx</tex>. Из-за того, что <tex>xAx</tex> {{---}} наибольший палиндром-суффикс строки <tex>p+xpx</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>.
Теперь нужно добавить суффиксную ссылку из вершины <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>O(n)</tex>.
== Применения ==
{{Задача
|definition=
Например, при добавлении символа <tex>a</tex> к строке <tex>aba</tex>, которая уже состоит из палиндромов <tex>a</tex>, <tex>b</tex> и <tex>aba</tex>, добавляется новый палиндром <tex>aa</tex>.
Мы знаем, что число новых подпалиндромов при добавлении символа <tex>0</tex> или <tex>1</tex>. Так что решение задачи довольно простое {{---}} будем строить дерево палиндромов символ за символом и для каждого нового символа отвечать, был ли добавлен новый палиндром или нет (определить это можно, например, по тому, были ли добавлены новые вершины к структуре).
Также данную структуру можно использовать для подсчета числа различных подпалиндромов строки. Это будет просто число вершин.
=== Число подпалиндромов ===
{{Задача
|definition=
Например, строка <tex>aba</tex> имеет четыре подпалиндрома: дважды <tex>a</tex>, <tex>b</tex> и <tex>aba</tex>.
Для решения задачи построим будем строить дерево палиндромов для данной строки. При обработке очередного символа добавим и на каждом шаге добавлять к ответу все палиндромы, которые содержат этот новый символ. Рассмотрим очередной шаг алгоритма после добавления символа <tex>x</tex>. Обозначим за <tex>t</tex> вершину, соответствующую максимальному палиндрому-суффиксу, содержащую этот последний символ. Заметим, что эти новые палиндромы , которые добавляет <tex>x</tex> {{---}} это новый максимальный палиндром-суффикс <tex>t'</tex>, который содержит новый символ, и а также все полиндромыпалиндромы, достижимые из <tex>t</tex> по суффиксным ссылкам(т.к. только они содержат новый символ <tex>x</tex>). Для того чтобы быстро найти их количество число, будем хранить в каждой вершине дерева палиндромов длину цепочки суффиксных ссылок до корня (включая саму вершину), а затем будем просто прибавлять к ответу это число для каждого очередного <tex>t</tex> по мере добавления новых символов.
Эта задача также может быть решена [[Алгоритм_Манакера|алгоритмом Манакера]] за ту же асимптотику, однако данный алгоритм не может быть расширен для более широкого класса задач, в отличие от дерева палиндромов.
{{Задача
|definition=
Необходимо найти число вхождений каждого подпалиндрома строки в нее неё саму.}}
Чтобы решить эту задачу деревом палиндромов, нужно обратить внимание на то, что при добавлении нового символа увеличивается количество вхождений наибольшего палиндрома-суффикса <tex>t</tex>, содержащего новый символ, и всех палиндромов, достижимых из <tex>t</tex> по суффиксным ссылкам.
Для решения данной задачи применим тот же алгоритм, что и в прошлой задаче, а затем пройдем по всем вершинам дерева палиндромов и выберем подходящую.
== См. также ==
* [[Сжатое суффиксное дерево]]
* [[Суффиксный массив]]
== Примечания ==
<references/>
== Источники информации ==
* [http://adilet.org/blog/25-09-14/ http://adiletAdilet.org/ {{---}} Palindromic tree {{---}} , Adilet ADJA Zhaxybay]
[[Категория:Алгоритмы и структуры данных]]
