165
правок
Изменения
Нет описания правки
== Описание структуры ==
Дерево палиндромов состоит из вершин. Каждая вершина соответствует палиндрому. Через <tex>u.value</tex> будем обозначать строку, которой соответствует вершина <tex>u</tex>.
[[Файл:palindromic_tree_nodespalindrome_tree_nodes.png|Пример четырех вершин дерева палиндромов|border]]
Ребра дерева палиндромов ориентированные и помечены символами. Ребро с символом <tex>x</tex> из вершины <tex>u</tex> в вершину <tex>v</tex> означает, что <tex>v.value=x+u.value+x</tex>
[[Файл:palindromic_tree_edgespalindrome_tree_edges.png|В данном примере мы получаем палиндром aba добавлением символа a к обоим сторонам палиндрома b|border]]
Также в дереве палиндромов присутствуют ''суффиксные ссылки''. Суффиксная ссылка из вершины <tex>u</tex> ведет в вершину <tex>w</tex>, если <tex>w.value</tex> является наибольшим суффиксом строки <tex>u.value</tex>.
[[Файл:palindromic_tree_suffix_linkpalindrome_tree_suffix_link.png|Мы добавили суффиксную ссылку (пунктирная линия) из aba к a потому, что a является наибольшим паллиндромом-суффиксом строки aba|border]]
== Построение Реализация ==//Название структуры данных, выбрано не совсем удачно, т.к. на самом деле в структуре хранится два
== Оценка сложности ==
