== Реализация ==
Название структуры данных выбрано не совсем удачно, т.к. на самом деле она представляет из себя два дерева, однако суффиксные ссылки могут вести как в то же, так и в другое дерево. Это сделано для удобства реализации. Также в целях экономии памяти мы будем хранить для каждой вершины не строки, а позицию в исходной строке (<tex>u.pos</tex>) и размер палиндрома (<tex>u.len</tex>).
Итак, у нас будет два дерева. Одно дерево для палиндромов четной длины, другое {{---}} для палиндромов нечетной длины. Каждое дерево будет иметь фиктивный корень.
Обозначим корни четного и нечетного дерева соответственно <tex>root_{even}</tex> и <tex>root_{odd}</tex>.
<tex>root_{odd}</tex> будет соответствовать фиктивному палиндрому длины -1. Это нужно для того, чтобы не обрабатывать отдельно случай добавления палиндрома длины 1. Теперь каждый раз при добавлении новой вершины <tex>u</tex> к вершине <tex>v</tex> мы будем просто указывать ее длину равной <tex>u.len = v.len + 2</tex>.
<tex>root_{even}</tex> будет соответствовать фиктивному палиндрому длины 0.
Также направим
== Оценка сложности ==
