Дерево палиндромов — различия между версиями
| Строка 6: | Строка 6: | ||
== Описание структуры == | == Описание структуры == | ||
Дерево палиндромов состоит из вершин. Каждая вершина соответствует палиндрому. Через <tex>u.value</tex> будем обозначать строку, которой соответствует вершина <tex>u</tex>. | Дерево палиндромов состоит из вершин. Каждая вершина соответствует палиндрому. Через <tex>u.value</tex> будем обозначать строку, которой соответствует вершина <tex>u</tex>. | ||
| − | [[Файл: | + | [[Файл:palindrome_tree_nodes.png|Пример четырех вершин дерева палиндромов|border]] |
Ребра дерева палиндромов ориентированные и помечены символами. Ребро с символом <tex>x</tex> из вершины <tex>u</tex> в вершину <tex>v</tex> означает, что <tex>v.value=x+u.value+x</tex> | Ребра дерева палиндромов ориентированные и помечены символами. Ребро с символом <tex>x</tex> из вершины <tex>u</tex> в вершину <tex>v</tex> означает, что <tex>v.value=x+u.value+x</tex> | ||
| − | [[Файл: | + | [[Файл:palindrome_tree_edges.png|В данном примере мы получаем палиндром aba добавлением символа a к обоим сторонам палиндрома b|border]] |
Также в дереве палиндромов присутствуют ''суффиксные ссылки''. Суффиксная ссылка из вершины <tex>u</tex> ведет в вершину <tex>w</tex>, если <tex>w.value</tex> является наибольшим суффиксом строки <tex>u.value</tex>. | Также в дереве палиндромов присутствуют ''суффиксные ссылки''. Суффиксная ссылка из вершины <tex>u</tex> ведет в вершину <tex>w</tex>, если <tex>w.value</tex> является наибольшим суффиксом строки <tex>u.value</tex>. | ||
| − | [[Файл: | + | [[Файл:palindrome_tree_suffix_link.png|Мы добавили суффиксную ссылку (пунктирная линия) из aba к a потому, что a является наибольшим паллиндромом-суффиксом строки aba|border]] |
| − | + | == Построение == | |
| − | == | + | == Реализация == |
| + | //Название структуры данных, выбрано не совсем удачно, т.к. на самом деле в структуре хранится два | ||
== Оценка сложности == | == Оценка сложности == | ||
Версия 11:37, 6 июня 2016
Дерево палиндромов — структура данных, позволяющая решить некоторые интересные задачи на палиндромы.
Эту структуру данных придумал Михаил Рубинчик и рассказал ее на летних сборах в Петрозаводске в 2014 году.
Содержание
Описание структуры
Дерево палиндромов состоит из вершин. Каждая вершина соответствует палиндрому. Через будем обозначать строку, которой соответствует вершина .
Ребра дерева палиндромов ориентированные и помечены символами. Ребро с символом из вершины в вершину означает, что В данном примере мы получаем палиндром aba добавлением символа a к обоим сторонам палиндрома b
Также в дереве палиндромов присутствуют суффиксные ссылки. Суффиксная ссылка из вершины ведет в вершину , если является наибольшим суффиксом строки .
Построение
Реализация
//Название структуры данных, выбрано не совсем удачно, т.к. на самом деле в структуре хранится два
