Дерево палиндромов

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

Эту структуру данных придумал Михаил Рубинчик и рассказал её на летних сборах в Петрозаводске в 2014 году. Наиболее подробное о дереве палиндромов или овердреве (palindromic tree, eertree) можно прочитать в диссертации Михаил Рубинчика [1]

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

Дерево палиндромов состоит из вершин, каждая из которых соответствует палиндрому. Все вершины соответствуют разным палиндромам. Через [math]u'[/math] будем обозначать строку, которой соответствует вершина [math]u[/math]. Рёбра дерева палиндромов ориентированные и помечены символами. Ребро с символом [math]x[/math] ведет из вершины [math]u[/math] в вершину [math]v[/math] тогда и только тогда, когда [math]v'=xu'x[/math].

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

Помимо вершин и рёбер в дереве палиндромов также присутствуют суффиксные ссылки. Для каждой вершины [math]u[/math] её суффиксная ссылка ведет в такую вершину [math]w[/math], что [math]w'[/math] является наибольшим суффиксом строки [math]u'[/math] относительно других вершин. При этом важно понимать, что суффиксная ссылка из вершины одного дерева может вести как в то же, так и в другое дерево.

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

Итак, структура будет состоять из двух деревьев и, соответственно, двух корней. Для удобства реализации каждый корень будет соответствовать фиктивной строке.

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

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

Построение

Опишем далее по шагам процесс построения дерева палиндромов для данной строки. Изначально оно состоит из двух фиктивных вершин, а далее будет достраиваться инкрементально после каждого рассмотренного символа строки.

Будем обрабатывать строку символ за символом. Пусть мы уже обработали некоторый префикс [math]p[/math] и теперь хотим добавить следующий символ строки, назовем его [math]x[/math].
Будем также поддерживать максимальный палиндром-суффикс обработанного префикса [math]p[/math]. Назовем его [math]t[/math].
Т.к. [math]t[/math] находится в уже обработанной части строки, то ему соответствует какая-то вершина в дереве. У этой вершины есть суффиксная ссылка на какую-то другую вершину, у которой тоже есть суффиксная ссылка и т.д.
Найдем теперь палиндром-суффикс строки [math]px[/math] (т.е. нового префикса). Искомая строка будет иметь вид [math]xAx[/math], где [math]A[/math] — какая-то строка, возможно пустая (или фиктивная строка длины [math]-1[/math], соответствующая корню [math]root_{odd}[/math], если искомый палиндром-суффикс — это просто символ [math]x[/math]). Т.к. [math]xAx[/math] — палиндром, то [math]A[/math] — тоже палиндром, и, более того, это суффикс строки [math]p[/math]. Поэтому он может быть достигнут из [math]t[/math] по суффиксным ссылкам.

Утверждение (1):

Строка [math]xAx[/math] — это единственная подстрока-палиндром строки [math]px[/math], которой, возможно, нет в [math]p[/math] (т.е. все другие подстроки-палиндромы есть).

[math]\triangleright[/math]

Заметим, что все новые подстроки-палиндромы, которых не было в [math]p[/math], должны оканчиваться на символ [math]x[/math], и поэтому должны быть палиндромом-суффиксом строки [math]px[/math]. Из-за того, что [math]xAx[/math] — наибольший палиндром-суффикс строки [math]px[/math], все остальные меньшие палиндромы-суффиксы этой строки уже есть в каком-то префиксе строки [math]xAx[/math] (т.к. для каждого суффикса палиндрома есть равный ему префикс) и, соответственно, уже есть в [math]p[/math].

[math]\triangleleft[/math]

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

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

Утверждение (2):

Очередная добавленная вершина [math]u[/math] не может быть максимальным палиндромом-суффиксом какой-либо ранее добавленной вершины [math]v[/math]

[math]\triangleright[/math]

Предположим, что это не так. Тогда оказывается, что не все подпалиндромы строки [math]v'[/math] были добавлены в дерево палиндромов ранее. А это противоречит утверждению 1.

[math]\triangleleft[/math]

Таким образом, добавление очередного символа по описанному алгоритму происходит корректно.

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

Память

Каждая вершина в дереве соответствует подпалиндрому, всего различных подпалиндромов в строке не более [math]n[/math] (т.к. при добавлении очередного символа появляется не более одного нового палиндрома). Поэтому дерево палиндромов занимает [math]O(n)[/math] памяти.

Время

Чтобы оценить временную сложность алгоритма, нужно заметить, что по мере того, как мы обрабатываем строку символ за символом, левая граница наибольшего палиндрома-суффикса уже обработанной строки сдвигается только вправо. Очевидно, эта граница может двигаться вправо не более [math]n[/math], где [math]n[/math] — длина строки, для которой мы строим дерево. То же самое относится и к левой границе той строки, на которую ведет суффиксная ссылка вновь добавленной вершины.

Таким образом, суммарное время работы построения алгоритма [math]O(n)[/math].

Применения

Число новых палиндромов, порождаемых очередным символом

Задача:

Необходимо определить число подпалиндромов, которые будут новыми после добавления символа [math]x[/math] в конец строки [math]s[/math].

Например, при добавлении символа [math]a[/math] к строке [math]aba[/math], которая уже состоит из палиндромов [math]a[/math], [math]b[/math] и [math]aba[/math], добавляется новый палиндром [math]aa[/math].

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

Также данную структуру можно использовать для подсчета числа различных подпалиндромов строки. Это будет просто число вершин.

Число подпалиндромов

Задача:

Требуется определить число подпалиндромов, которые содержатся в данной строке.

Например, строка [math]aba[/math] имеет четыре подпалиндрома: дважды [math]a[/math], [math]b[/math] и [math]aba[/math].

Для решения задачи будем строить дерево палиндромов для данной строки и на каждом шаге добавлять к ответу все палиндромы, которые содержат этот новый символ.

Рассмотрим очередной шаг алгоритма после добавления символа [math]x[/math]. Обозначим за [math]t[/math] вершину, соответствующую максимальному палиндрому-суффиксу, содержащую этот последний символ. Заметим, что новые палиндромы, которые добавляет [math]x[/math] — это [math]t'[/math], а также все палиндромы, достижимые из [math]t[/math] по суффиксным ссылкам (т.к. только они содержат новый символ [math]x[/math]). Для того чтобы быстро найти их число, будем хранить в каждой вершине длину цепочки суффиксных ссылок до корня (включая саму вершину), а затем будем просто прибавлять к ответу это число для каждого очередного [math]t[/math] по мере добавления новых символов.

Эта задача также может быть решена алгоритмом Манакера за ту же асимптотику, однако данный алгоритм не может быть расширен для более широкого класса задач, в отличие от дерева палиндромов.

Число вхождений каждого подпалиндрома в строку

Задача:

Необходимо найти число вхождений каждого подпалиндрома строки в неё саму.

Чтобы решить эту задачу деревом палиндромов, нужно обратить внимание на то, что при добавлении нового символа увеличивается количество вхождений наибольшего палиндрома-суффикса [math]t[/math], содержащего новый символ, и всех палиндромов, достижимых из [math]t[/math] по суффиксным ссылкам.

Для каждой вершины [math]u[/math] дерева палиндромов будем хранить число вхождений строки [math]u'[/math] в исходную строку (не обязательно актуальные данные) и число, которое необходимо добавить к числу вхождений всех потомков [math]v[/math] вершины [math]u[/math]. Назовем такую операцию добавления операцией релаксации. После того, как релаксация будет выполнена для всех предков вершины [math]u[/math], можно будет считать, что посчитанное число вхождений соответствует действительности.

Данный метод очень похож на метод, описанный в статье про реализацию массовых обновлений в деревьях отрезков.

Поиск рефрен-палиндрома

Задача:

Для данной строки необходимо найти палиндром, произведение длины которого на количество вхождений в строку является максимальным.

Для решения данной задачи применим тот же алгоритм, что и в прошлой задаче, а затем пройдем по всем вершинам дерева палиндромов и выберем подходящую.

См. также

• Алгоритм Манакера
• Сжатое суффиксное дерево
• Суффиксный массив

Источники информации

• Adilet.org — Palindromic tree, Adilet ADJA Zhaxybay