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

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

Эту структуру данных придумал Михаил Рубинчик и рассказал ее на летних сборах в Петрозаводске в 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]/todo[/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].

So, to process new letter x we just go along suffix links of t until we find an appropriate A (and we always find some, possibly of length -1 if we trace suffix links back to the roots). Then we check if there is an edge on letter x from the node corresponding to A, and if not, set this edge going to the new node corresponding to xAx.

What about suffix link of the node xAx? If this node already existed before, the suffix link was also already set and we don't need to do anything. If not, then we need to find the largest suffix-palindrome of xAx, which will be in a form of xBx, where B is some string, possibly empty. By the same logic that we used before, B is a suffix-palindrome of p and can be reached from t by suffix links.

Источники

• Palindromic tree