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

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

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

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

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

Суффиксные ссылки обоих корней будут вести к вершине [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] по суффиксным ссылкам.

Утверждение:

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

[math]\triangleright[/math]

Заметим, что все новые подстроки-палиндромы, которых не было в [math]p[/math], должны оканчиваться на символ [math]x[/math], и поэтому должны быть палиндромом-суффиксом строки [math]p+x[/math]. Из-за того, что [math]xAx[/math] — наибольший палиндром-суффикс строки [math]p+x[/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] по суффиксным ссылкам.

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

Память

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

Время

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

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

Реализация

Рассмотрим пример реализации дерева палиндромов. Будем считать, что каждая вершина имеет номер. Свободный для очередной вершины номер будем хранить в переменной [math]sz[/math].

Для каждой вершины будем хранить длину палиндрома, суффиксную ссылку и массив ребер. В реализации им будут соответствовать массивы [math]len[\mathrm{MAXN}][/math], [math]suff\_link[\mathrm{MAXN}][/math] и [math]to[\mathrm{MAXN}][\mathrm{ALPHABET\_SIZE}][/math] соответственно. Также будем хранить саму строку и длину ее обработанной части [math]n[/math]. В переменной [math]last[/math] будем хранить последнюю добавленную вершину.

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;
}

Вспомогательная функция, которая спускается начиная с вершины [math]v[/math] по суффиксным ссылкам до тех пор, пока не придет в палиндром-суффикс [math]xAx[/math]. Тут [math]x[/math] — последний добавленный символ, а [math]A[/math] — некоторый палиндром.

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];
}

Чтобы построить дерево палиндромов, нужно просто для каждого символа исходной строки последовательно вызвать [math]\mathrm{add\_letter}[/math].

Применения

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

Задача:

Уметь отвечать на вопрос [math]``[/math]как много новых палиндромов-подстрок появится у строки [math]s[/math], если к ней в конец добавить символ [math]x"[/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]``[/math] как много подпалиндромов имеет данная строка [math]"[/math].

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

Для решения задачи построим дерево палиндромов для данной строки. При обработке очередного символа добавим к ответу все палиндромы, которые содержат этот новый символ. Заметим, что эти палиндромы — это новый максимальный палиндром-суффикс [math]t[/math], который содержит новый символ, и все полиндромы, достижимые из [math]t[/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], можно будет считать, что посчитанное число вхождений соответствует действительности.

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

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

Задача:

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

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

См. также

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

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

• http://adilet.org/ — Palindromic tree — Adilet ADJA Zhaxybay