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