Дерево палиндромов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
'''Дерево палиндромов''' {{---}} описание
+
'''Дерево палиндромов''' {{---}} структура данных, позволяющая решить некоторые интересные задачи на палиндромы.
 +
 
 +
Эту структуру данных придумал [http://codeforces.com/profile/MikhailRubinchik Михаил Рубинчик] и рассказал ее на летних сборах в Петрозаводске в 2014 году.
 +
 
  
 
== Описание структуры ==
 
== Описание структуры ==
 +
Дерево палиндромов состоит из вершин. Каждая вершина соответствует палиндрому. Через <tex>u.value</tex> будем обозначать строку, которой соответствует вершина <tex>u</tex>.
 +
[[Файл:palindromic_tree_nodes.png|Пример четырех вершин дерева палиндромов|border]]
 +
 +
Ребра дерева палиндромов ориентированные и помечены символами. Ребро с символом <tex>x</tex> из вершины <tex>u</tex> в вершину <tex>v</tex> означает, что <tex>v.value=x+u.value+x</tex>
 +
[[Файл:palindromic_tree_edges.png|В данном примере мы получаем палиндром aba добавлением символа a к обоим сторонам палиндрома b|border]]
 +
 +
Также в дереве палиндромов присутствуют ''суффиксные ссылки''. Суффиксная ссылка из вершины <tex>u</tex> ведет в вершину <tex>w</tex>, если <tex>w.value</tex> является наибольшим суффиксом строки <tex>u.value</tex>.
 +
[[Файл:palindromic_tree_suffix_link.png|Мы добавили суффиксную ссылку (пунктирная линия) из aba к a потому, что a является наибольшим паллиндромом-суффиксом строки aba|border]]
 +
 +
Название структуры данных, по видимому, выбрано неудачно, т.к.
  
 
== Построение ==
 
== Построение ==

Версия 22:39, 5 июня 2016

Дерево палиндромов — структура данных, позволяющая решить некоторые интересные задачи на палиндромы.

Эту структуру данных придумал Михаил Рубинчик и рассказал ее на летних сборах в Петрозаводске в 2014 году.


Описание структуры

Дерево палиндромов состоит из вершин. Каждая вершина соответствует палиндрому. Через [math]u.value[/math] будем обозначать строку, которой соответствует вершина [math]u[/math]. Пример четырех вершин дерева палиндромов

Ребра дерева палиндромов ориентированные и помечены символами. Ребро с символом [math]x[/math] из вершины [math]u[/math] в вершину [math]v[/math] означает, что [math]v.value=x+u.value+x[/math] В данном примере мы получаем палиндром aba добавлением символа a к обоим сторонам палиндрома b

Также в дереве палиндромов присутствуют суффиксные ссылки. Суффиксная ссылка из вершины [math]u[/math] ведет в вершину [math]w[/math], если [math]w.value[/math] является наибольшим суффиксом строки [math]u.value[/math]. Мы добавили суффиксную ссылку (пунктирная линия) из aba к a потому, что a является наибольшим паллиндромом-суффиксом строки aba

Название структуры данных, по видимому, выбрано неудачно, т.к.

Построение

Оценка сложности

Применения

Источники