165
правок
Изменения
→Описание структуры
Также в дереве палиндромов присутствуют ''суффиксные ссылки''. Суффиксная ссылка из вершины <tex>u</tex> ведет в вершину <tex>w</tex>, если <tex>w.value</tex> является наибольшим суффиксом строки <tex>u.value</tex>.
[[Файл:palindrome_tree_suffix_link.png|Мы добавили суффиксную ссылку (пунктирная линия) из aba к a потому, что a является наибольшим паллиндромом-суффиксом строки aba|border]]
Название структуры данных выбрано не совсем удачно, т.к. на самом деле она представляет из себя два дерева, однако суффиксные ссылки могут вести как в то же, так и в другое дерево. Это сделано для удобства реализации. Также в целях экономии памяти мы не будем хранить для каждой вершины соответствующую ей строку-палиндром. Вместо этого мы будем хранить только длину палиндрома.
Итак, у нас будет два дерева. Одно дерево для палиндромов четной длины, другое {{---}} для палиндромов нечетной длины. Каждое дерево будет иметь фиктивный корень.
Обозначим корни четного и нечетного дерева соответственно <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.
Также направим суффиксные ссылки обоих корней к вершине <tex>root_{odd}</tex>. Это нужно для того, чтобы <tex>/todo</tex>.
== Построение ==
