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

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

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

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

Дерево палиндромов состоит из вершин. Каждая вершина соответствует палиндрому. Через [math]u.value[/math] будем обозначать строку, которой соответствует вершина [math]u[/math].

Ребра дерева палиндромов ориентированные и помечены символами. Ребро с символом [math]x[/math] из вершины [math]u[/math] в вершину [math]v[/math] означает, что [math]v.value=x+u.value+x[/math]. Тут [math]``+"[/math] означает конкатенацию строк.

Также в дереве палиндромов присутствуют суффиксные ссылки. Суффиксная ссылка из вершины [math]u[/math] ведет в вершину [math]w[/math], если [math]w.value[/math] является наибольшим суффиксом строки [math]u.value[/math].

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

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

[math]root_{odd}[/math] будет соответствовать фиктивному палиндрому длины -1. Это нужно для того, чтобы не обрабатывать отдельно случай добавления палиндрома длины 1. Теперь каждый раз при добавлении новой вершины [math]u[/math] к вершине [math]v[/math] мы будем просто указывать ее длину равной [math]u.len = v.len + 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]p[/math] и [math]x[/math]. Искомый палиндром-суффикс будет иметь вид [math]``xAx"[/math], где [math]A[/math] — это какая-то строка, возможно пустая (или фиктивный строка длины -1, соответствующая корню [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]p[/math], должны оканчиваться на символ [math]x[/math], и поэтому должны быть палиндромом-суффиксом строки [math]p+x[/math]. Из-за того, что [math]xAx[/math] — наибольший палиндром-суффикс строки [math]p+x[/math], все остальные меньшие палиндромы-суффиксы этой строки уже есть в каком-то префиксе строки [math]xAx[/math] (т.к. для каждого суффикса палиндрома есть равный ему префикс) и, соответственно, уже есть в [math]p[/math].

Таким образом, чтобы обработать очередной символ [math]x[/math], нужно просто спуститься по суффиксным ссылкам строки [math]t[/math] до тех пор, пока мы не найдем подходящую строку [math]A[/math] (причем мы всегда можем найти такую строку, возможно длины -1, если очередная суффиксная ссылка будет вести в корень). Затем нужно проверить, есть ли уже ребро по символу [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;
    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(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.num[/math] — количество вхождений соответствующего вершине палиндрома в исходную строку (не обязательно актуальные данные) и число [math]u.toAdd[/math], которое необходимо добавить к [math]v.num[/math] всех потомков [math]v[/math] вершины [math]u[/math]. Назовем такую операцию операцией релаксации. После того, как релаксация будет выполнена для всех предков вершины [math]u[/math], можно будет считать, что [math]u.num[/math] содержит актуальные данные. Данный метод очень похож на метод, описанный в статье про реализацию массовых обновлений в деревьях отрезков.

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

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

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

Источники

• Palindromic tree