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

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

Эту структуру данных придумал Михаил Рубинчик и рассказал ее на летних сборах в Петрозаводске в 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]u[/math] ведет в вершину [math]w[/math], если [math]w.value[/math] является наибольшим суффиксом строки [math]u.value[/math].

Реализация

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

Итак, у нас будет два корня.

Источники

• Palindromic tree