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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание структуры)
м (rollbackEdits.php mass rollback)
 
(не показаны 52 промежуточные версии 7 участников)
Строка 1: Строка 1:
 
'''Дерево палиндромов''' (англ. ''palindromic tree'') {{---}} структура данных, позволяющая решить некоторые интересные задачи на палиндромы.  
 
'''Дерево палиндромов''' (англ. ''palindromic tree'') {{---}} структура данных, позволяющая решить некоторые интересные задачи на палиндромы.  
  
Эту структуру данных придумал Михаил Рубинчик<ref name="ref1">[http://codeforces.com/profile/MikhailRubinchik MikhailRubinchik - Codeforces]</ref> и рассказал ее на летних сборах в Петрозаводске в 2014 году.
+
Эту структуру данных придумал Михаил Рубинчик<ref name="ref1">[http://codeforces.com/profile/MikhailRubinchik Codeforces {{---}} MikhailRubinchik]</ref> и рассказал её на летних сборах в Петрозаводске в 2014 году. Наиболее подробное о дереве палиндромов или овердреве (palindromic tree, eertree) можно прочитать в диссертации Михаил Рубинчика [http://www.pdmi.ras.ru/pdmi/dissertatiton/2016-05-25t000000-%D1%80%D1%83%D0%B1%D0%B8%D0%BD%D1%87%D0%B8%D0%BA-%D0%BC%D0%B8%D1%85%D0%B0%D0%B8%D0%BB-%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%B8%D0%BD%D0%BE%D0%B2%D0%B8%D1%87]
  
 
== Описание структуры ==
 
== Описание структуры ==
Дерево палиндромов состоит из вершин. Каждая вершина соответствует палиндрому. Через <tex>u'</tex> будем обозначать строку, которой соответствует вершина <tex>u</tex>.
+
[[Дерево,_эквивалентные_определения|Дерево]] палиндромов состоит из вершин, каждая из которых соответствует палиндрому. Все вершины соответствуют разным палиндромам. Через <tex>u'</tex> будем обозначать строку, которой соответствует вершина <tex>u</tex>.
Ребра дерева палиндромов ориентированные и помечены символами. Если ребро с символом <tex>x</tex> из вершины <tex>u</tex> в вершину <tex>v</tex> тогда и только тогда, когда <tex>v'=xu'x</tex>.  
+
[[Основные_определения_теории_графов#def_graph_edge_1|Рёбра]] дерева палиндромов ориентированные и помечены символами. Ребро с символом <tex>x</tex> ведет из вершины <tex>u</tex> в вершину <tex>v</tex> тогда и только тогда, когда <tex>v'=xu'x</tex>.
  
 
[[Файл:palindrome_tree_nodes.png|Пример четырех вершин дерева палиндромов|border]] [[Файл:palindrome_tree_edge.png|В данном примере мы получаем палиндром aba добавлением символа a к обоим сторонам палиндрома b|border]]
 
[[Файл:palindrome_tree_nodes.png|Пример четырех вершин дерева палиндромов|border]] [[Файл:palindrome_tree_edge.png|В данном примере мы получаем палиндром aba добавлением символа a к обоим сторонам палиндрома b|border]]
  
Также в дереве палиндромов присутствуют ''суффиксные ссылки''. Суффиксная ссылка из вершины <tex>u</tex> ведет в вершину <tex>w</tex>, если <tex>w'</tex> является наибольшим суффиксом строки <tex>u'</tex>.
 
[[Файл:palindrome_tree_suffix_link.png|Мы добавили суффиксную ссылку (пунктирная линия) из aba к a потому, что a является наибольшим паллиндромом-суффиксом строки aba|border]]
 
  
 +
Стоит обратить внимание на то, что название структуры данных выбрано не совсем удачно. На самом деле структура представляет из себя два дерева {{---}} одно для палиндромов чётной длины, другое для палиндромов нечётной длины. Обозначим корни этих деревьев за <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]]
  
Итак, у нас будет два дерева. Одно дерево для палиндромов четной длины, другое {{---}} для палиндромов нечетной длины. Каждое дерево будет иметь фиктивный корень.
 
Обозначим корни четного и нечетного дерева соответственно <tex>root_{even}</tex> и <tex>root_{odd}</tex>.
 
  
<tex>root_{odd}</tex> будет соответствовать фиктивному палиндрому длины <tex>-1</tex>. Это нужно для того, чтобы не обрабатывать отдельно случай добавления палиндрома длины 1. Теперь каждый раз при добавлении новой вершины <tex>u</tex> к вершине <tex>v</tex> мы будем просто указывать ее длину равной <tex>u.len = v.len + 2</tex>.
+
При реализации в целях экономии памяти мы не будем хранить для каждой вершины соответствующую ей строку-палиндром. Этот подход был бы неэффективным с точки зрения памяти. Вместо этого мы будем хранить только длину палиндрома (и для некоторых задач позицию палиндрома в строке).
  
<tex>root_{even}</tex> будет соответствовать фиктивному палиндрому длины 0.
+
Итак, структура будет состоять из двух деревьев и, соответственно, двух корней. Для удобства реализации каждый корень будет соответствовать фиктивной строке.
 +
* <tex>root_{odd}</tex> будет соответствовать палиндрому длины <tex>-1</tex>. Это нужно для того, чтобы не обрабатывать отдельно случай добавления палиндрома длины <tex>1</tex>. Теперь каждый раз при добавлении ребра из вершины <tex>u</tex> к вершине <tex>v</tex>, мы будем просто считать что <tex>|v'|=|u'| + 2</tex>.
 +
* <tex>root_{even}</tex> будет соответствовать фиктивному палиндрому длины <tex>0</tex>.
  
Также направим суффиксные ссылки обоих корней к вершине <tex>root_{odd}</tex>.
+
Суффиксные ссылки обоих корней будут вести к вершине <tex>root_{odd}</tex>. Это соглашение нужно также для удобства реализации {{---}} теперь каждая вершина имеет суффиксную ссылку.
  
 
== Построение ==
 
== Построение ==
Будем обрабатывать строку символ за символом. Пусть мы уже обработали некоторый префикс <tex>p</tex> и теперь хотим добавить следующий символ строки, назовем его <tex>x</tex>.
+
Опишем далее по шагам процесс построения дерева палиндромов для данной строки. Изначально оно состоит из двух фиктивных вершин, а далее будет достраиваться инкрементально после каждого рассмотренного символа строки.
 
 
[[Файл:palindrome_tree_build1.png|border]]
 
  
Будем также поддерживать максимальный палиндром-суффикс обработанного префикса <tex>p</tex>. Назовем его <tex>t</tex>.
+
{| style="background-color:#CCC;margin:0.5px"
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"|Будем обрабатывать строку символ за символом. Пусть мы уже обработали некоторый префикс <tex>p</tex> и теперь хотим добавить следующий символ строки, назовем его <tex>x</tex>.
 +
|style="background-color:#FFF;padding:2px 30px"|[[Файл:palindrome_tree_build1.png|500px]]
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"|Будем также поддерживать максимальный палиндром-суффикс обработанного префикса <tex>p</tex>. Назовем его <tex>t</tex>.
 +
|style="background-color:#FFF;padding:2px 30px"|[[Файл:palindromic_tree_nodes.png|500px]]
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"|Т.к. <tex>t</tex> находится в уже обработанной части строки, то ему соответствует какая-то вершина в дереве. У этой вершины есть суффиксная ссылка на какую-то другую вершину, у которой тоже есть суффиксная ссылка и т.д.
 +
|style="background-color:#FFF;padding:2px 30px"|[[Файл:palindrome_tree_build3.png|500px|Цепочка суффиксных ссылок из t]]
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"|Найдем теперь палиндром-суффикс строки <tex>px</tex> (т.е. нового префикса). Искомая строка будет иметь вид <tex>xAx</tex>, где <tex>A</tex> {{---}} какая-то строка, возможно пустая (или фиктивная строка длины <tex>-1</tex>, соответствующая корню <tex>root_{odd}</tex>, если искомый палиндром-суффикс {{---}} это просто символ <tex>x</tex>).
 +
Т.к. <tex>xAx</tex> {{---}} палиндром, то <tex>A</tex> {{---}} тоже палиндром, и, более того, это суффикс строки <tex>p</tex>. Поэтому он может быть достигнут из <tex>t</tex> по суффиксным ссылкам.
 +
|style="background-color:#FFF;padding:2px 30px"|[[Файл:palindrome_tree_build4.png|500px]]
 +
|}
  
[[Файл:palindromic_tree_nodes.png|border]]
 
  
Т.к. <tex>t</tex> находится в уже обработанной части строки, то ему соответствует какая-то вершина в дереве. У этой вершины есть суффиксная ссылка на какую-то другую вершину, у которой тоже есть суффиксная ссылка и т.д.
+
{{Утверждение
 +
|author=1
 +
|statement=
 +
Строка <tex>xAx</tex> {{---}} это единственная подстрока-палиндром строки <tex>px</tex>, которой, возможно, нет в <tex>p</tex> (т.е. все другие подстроки-палиндромы есть).  
 +
|proof=
 +
Заметим, что все новые подстроки-палиндромы, которых не было в <tex>p</tex>, должны оканчиваться на символ <tex>x</tex>, и поэтому должны быть палиндромом-суффиксом строки <tex>px</tex>. Из-за того, что <tex>xAx</tex> {{---}} наибольший палиндром-суффикс строки <tex>px</tex>, все остальные меньшие палиндромы-суффиксы этой строки уже есть в каком-то префиксе строки <tex>xAx</tex> (т.к. для каждого суффикса палиндрома есть равный ему префикс) и, соответственно, уже есть в <tex>p</tex>.}}
  
[[Файл:palindrome_tree_build3.png|Цепочка суффиксных ссылок из t|border]]
+
Таким образом, чтобы обработать очередной символ <tex>x</tex>, нужно просто спуститься по суффиксным ссылкам вершины <tex>t</tex> до тех пор, пока мы не найдем подходящую строку <tex>A</tex> (причем мы всегда можем найти такую строку, возможно длины <tex>-1</tex>, если очередная суффиксная ссылка будет вести в корень). Затем нужно проверить, есть ли уже ребро по символу <tex>x</tex> из вершины, соответствующей <tex>A</tex>, и если нет, добавить это ребро в новую вершину <tex>xAx</tex>.
  
Найдем теперь палиндром-суффикс нового префикса, состоящего из <tex>p</tex> и <tex>x</tex>. Искомый палиндром-суффикс будет иметь вид <tex>xAx</tex>, где <tex>A</tex> {{---}} какая-то строка, возможно пустая (или фиктивный строка длины <tex>-1</tex>, соответствующая корню <tex>root_{odd}</tex>, если искомый палиндром-суффикс {{---}} это просто символ <tex>x</tex>).  
+
Теперь нужно добавить суффиксную ссылку из вершины <tex>xAx</tex>. Если эта вершина уже существовала до добавления символа <tex>x</tex>, ничего делать не нужно {{---}} суффиксная ссылка и так указывает на правильную вершину. Иначе нужно найти наибольший палиндром-суффикс строки <tex>xAx</tex>, который будет иметь вид <tex>xBx</tex>, где <tex>B</tex> {{---}} это некоторая строка, возможно, пустая. Следуя той же логике, которую мы использовали раньше, <tex>B</tex> {{---}} это палиндром-суффикс строки <tex>p</tex> и может быть достигнут из <tex>t</tex> по суффиксным ссылкам.
Т.к. <tex>xAx</tex> палиндром, то <tex>A</tex> {{---}} тоже палиндром, и, более того, это суффикс строки <tex>p</tex>. Поэтому он может быть достигнут из <tex>t</tex> по суффиксным ссылкам.
 
  
[[Файл:palindrome_tree_build4.png|border]]
 
  
Строка <tex>xAx</tex> {{---}} это единственная подстрока-палиндром строки <tex>p+x</tex>, которой, возможно, нет в <tex>p</tex> (все другие подстроки-палиндромы есть). Чтобы понять почему это так, нужно обратить внимание на то, что все новые подстроки-палиндромы, которых не было в <tex>p</tex>, должны оканчиваться на символ <tex>x</tex>, и поэтому должны быть палиндромом-суффиксом строки <tex>p+x</tex>. Из-за того, что <tex>xAx</tex> {{---}} наибольший палиндром-суффикс строки <tex>p+x</tex>, все остальные меньшие палиндромы-суффиксы этой строки уже есть в каком-то префиксе строки <tex>xAx</tex> (т.к. для каждого суффикса палиндрома есть равный ему префикс) и, соответственно, уже есть в <tex>p</tex>.
+
{{Утверждение
 +
|author=2
 +
|statement=
 +
Очередная добавленная вершина <tex>u</tex> не может быть максимальным палиндромом-суффиксом какой-либо ранее добавленной вершины <tex>v</tex>
 +
|proof=
 +
Предположим, что это не так. Тогда оказывается, что не все подпалиндромы строки <tex>v'</tex> были добавлены в дерево палиндромов ранее. А это противоречит утверждению 1.
 +
}}
  
Таким образом, чтобы обработать очередной символ <tex>x</tex>, нужно просто спуститься по суффиксным ссылкам строки <tex>t</tex> до тех пор, пока мы не найдем подходящую строку <tex>A</tex> (причем мы всегда можем найти такую строку, возможно длины <tex>-1</tex>, если очередная суффиксная ссылка будет вести в корень). Затем нужно проверить, есть ли уже ребро по символу <tex>x</tex> из вершины, соответствующей <tex>A</tex>, и если нет, добавить это ребро в новую вершину <tex>xAx</tex>.
+
Таким образом, добавление очередного символа по описанному алгоритму происходит корректно.
 
 
Теперь нужно добавить суффиксную ссылку из вершины <tex>xAx</tex>. Если эта вершина уже существовала до добавления символа <tex>x</tex>, ничего делать не нужно {{---}} суффиксная ссылка итак указывает на правильную вершину. Иначе на нужно найти наибольший палиндром-суффикс строки <tex>xAx</tex>, который будет иметь вид <tex>xBx</tex>, где <tex>B</tex> {{---}} это некоторая строка, возможно, пустая. Следуя той же логике, которую мы использовали раньше, <tex>B</tex> {{---}} это палиндром-суффикс строки <tex>p</tex> и может быть достигнут из <tex>t</tex> по суффиксным ссылкам.
 
  
 
== Оценка сложности ==
 
== Оценка сложности ==
  
 
=== Память ===
 
=== Память ===
Каждая вершина в дереве соответствует подпалиндрому, всего палиндромов в строке не более <tex>n</tex> (т.к. при добавлении очередного символа появляется не более одного нового палиндрома).  
+
Каждая вершина в дереве соответствует подпалиндрому, всего различных подпалиндромов в строке не более <tex>n</tex> (т.к. при добавлении очередного символа появляется не более одного нового палиндрома).  
 
Поэтому дерево палиндромов занимает <tex>O(n)</tex> памяти.
 
Поэтому дерево палиндромов занимает <tex>O(n)</tex> памяти.
  
Строка 58: Строка 77:
  
 
Таким образом, суммарное время работы построения алгоритма <tex>O(n)</tex>.
 
Таким образом, суммарное время работы построения алгоритма <tex>O(n)</tex>.
 
== Реализация ==
 
Рассмотрим пример реализации дерева палиндромов. Будем считать, что каждая вершина имеет номер. Свободный для очередной вершины номер будем хранить в переменной <tex>sz</tex>.
 
 
Для каждой вершины будем хранить длину палиндрома, суффиксную ссылку и массив ребер. В реализации им будут соответствовать массивы <tex>len[\mathrm{MAXN}]</tex>, <tex>suff\_link[\mathrm{MAXN}]</tex> и <tex>to[\mathrm{MAXN}][\mathrm{ALPHABET\_SIZE}]</tex> соответственно. Также будем хранить саму строку и длину ее обработанной части <tex>n</tex>. В переменной <tex>last</tex> будем хранить последнюю добавленную вершину.
 
 
'''int''' s[MAXN], len[MAXN], suff_link[MAXN], to[MAXN][ALPHABET_SIZE];
 
'''int''' n, sz, last;
 
 
В самом начале нужно инициализировать структуру.
 
 
'''void''' init() {
 
    n = 0;
 
    link[0] = 1;
 
    len[1] = -1;
 
    sz = 2;
 
}
 
 
Вспомогательная функция, которая спускается начиная с вершины <tex>v</tex> по суффиксным ссылкам до тех пор, пока не придет в палиндром-суффикс <tex>xAx</tex>. Тут <tex>x</tex> {{---}} последний добавленный символ, а <tex>A</tex> {{---}} некоторый палиндром.
 
 
'''int''' get_sufflink('''int''' v) {
 
    '''while''' (s[n - len[v] - 2] != s[n - 1]) v = suff_link[v];
 
    '''return''' v;
 
}
 
 
И, наконец, процедура добавления очередного символа в структуру:
 
 
'''void''' add_letter('''int''' c) {
 
    s[n++] = c;
 
    last = get_sufflink(last);
 
    '''if''' (!to[last][c]) {
 
        len[sz] = len[last] + 2;
 
        link[sz] = to[get_sufflink(link[last])][c];
 
        to[last][c] = sz++;
 
    }
 
    last = to[last][c];
 
}
 
 
Чтобы построить дерево палиндромов, нужно просто для каждого символа исходной строки последовательно вызвать <tex>\mathrm{add\_letter}</tex>.
 
  
 
== Применения ==
 
== Применения ==
Строка 102: Строка 82:
 
{{Задача
 
{{Задача
 
|definition=
 
|definition=
Уметь отвечать на вопрос <tex>``</tex>как много новых палиндромов-подстрок появится у строки <tex>s</tex>, если к ней в конец добавить символ <tex>x"</tex>.}}
+
Необходимо определить число подпалиндромов, которые будут новыми после добавления символа <tex>x</tex> в конец строки <tex>s</tex>.}}
  
 
Например, при добавлении символа <tex>a</tex> к строке <tex>aba</tex>, которая уже состоит из палиндромов <tex>a</tex>, <tex>b</tex> и <tex>aba</tex>, добавляется новый палиндром <tex>aa</tex>.
 
Например, при добавлении символа <tex>a</tex> к строке <tex>aba</tex>, которая уже состоит из палиндромов <tex>a</tex>, <tex>b</tex> и <tex>aba</tex>, добавляется новый палиндром <tex>aa</tex>.
  
 
Мы знаем, что число новых подпалиндромов при добавлении символа <tex>0</tex> или <tex>1</tex>. Так что решение задачи довольно простое {{---}} будем строить дерево палиндромов символ за символом и для каждого нового символа отвечать, был ли добавлен новый палиндром или нет (определить это можно, например, по тому, были ли добавлены новые вершины к структуре).
 
Мы знаем, что число новых подпалиндромов при добавлении символа <tex>0</tex> или <tex>1</tex>. Так что решение задачи довольно простое {{---}} будем строить дерево палиндромов символ за символом и для каждого нового символа отвечать, был ли добавлен новый палиндром или нет (определить это можно, например, по тому, были ли добавлены новые вершины к структуре).
 +
 +
 +
Также данную структуру можно использовать для подсчета числа различных подпалиндромов строки. Это будет просто число вершин.
  
 
=== Число подпалиндромов ===
 
=== Число подпалиндромов ===
 
{{Задача
 
{{Задача
 
|definition=
 
|definition=
Уметь отвечать на вопрос <tex>``</tex> как много подпалиндромов имеет данная строка <tex>"</tex>.}}
+
Требуется определить число подпалиндромов, которые содержатся в данной строке.}}
  
 
Например, строка <tex>aba</tex> имеет четыре подпалиндрома: дважды <tex>a</tex>, <tex>b</tex> и <tex>aba</tex>.
 
Например, строка <tex>aba</tex> имеет четыре подпалиндрома: дважды <tex>a</tex>, <tex>b</tex> и <tex>aba</tex>.
  
Для решения задачи построим дерево палиндромов для данной строки. При обработке очередного символа добавим к ответу все палиндромы, которые содержат этот новый символ. Заметим, что эти палиндромы {{---}} это новый максимальный палиндром-суффикс <tex>t</tex>, который содержит новый символ, и все полиндромы, достижимые из <tex>t</tex> по суффиксным ссылкам. Для того чтобы быстро найти их количество будем хранить в каждой вершине дерева палиндромов длину цепочки суффиксных ссылок (включая саму вершину), а затем будем просто прибавлять к ответу это число для каждого <tex>t</tex> по мере добавления новых символов.  
+
Для решения задачи будем строить дерево палиндромов для данной строки и на каждом шаге добавлять к ответу все палиндромы, которые содержат этот новый символ.  
 +
 
 +
Рассмотрим очередной шаг алгоритма после добавления символа <tex>x</tex>. Обозначим за <tex>t</tex> вершину, соответствующую максимальному палиндрому-суффиксу, содержащую этот последний символ.
 +
Заметим, что новые палиндромы, которые добавляет <tex>x</tex> {{---}} это <tex>t'</tex>, а также все палиндромы, достижимые из <tex>t</tex> по суффиксным ссылкам (т.к. только они содержат новый символ <tex>x</tex>). Для того чтобы быстро найти их число, будем хранить в каждой вершине длину цепочки суффиксных ссылок до корня (включая саму вершину), а затем будем просто прибавлять к ответу это число для каждого очередного <tex>t</tex> по мере добавления новых символов.  
 +
 
  
 
Эта задача также может быть решена [[Алгоритм_Манакера|алгоритмом Манакера]] за ту же асимптотику, однако данный алгоритм не может быть расширен для более широкого класса задач, в отличие от дерева палиндромов.
 
Эта задача также может быть решена [[Алгоритм_Манакера|алгоритмом Манакера]] за ту же асимптотику, однако данный алгоритм не может быть расширен для более широкого класса задач, в отличие от дерева палиндромов.
Строка 122: Строка 109:
 
{{Задача
 
{{Задача
 
|definition=
 
|definition=
Необходимо найти число вхождений каждого подпалиндрома строки в нее саму.}}
+
Необходимо найти число вхождений каждого подпалиндрома строки в неё саму.}}
  
 
Чтобы решить эту задачу деревом палиндромов, нужно обратить внимание на то, что при добавлении нового символа увеличивается количество вхождений наибольшего палиндрома-суффикса <tex>t</tex>, содержащего новый символ, и всех палиндромов, достижимых из <tex>t</tex> по суффиксным ссылкам.
 
Чтобы решить эту задачу деревом палиндромов, нужно обратить внимание на то, что при добавлении нового символа увеличивается количество вхождений наибольшего палиндрома-суффикса <tex>t</tex>, содержащего новый символ, и всех палиндромов, достижимых из <tex>t</tex> по суффиксным ссылкам.
  
Для каждой вершины <tex>u</tex> дерева палиндромов будем хранить число <tex>u.num</tex> {{---}} количество вхождений соответствующего вершине палиндрома в исходную строку (не обязательно актуальные данные) и число <tex>u.toAdd</tex>, которое необходимо добавить к <tex>v.num</tex> всех потомков <tex>v</tex> вершины <tex>u</tex>. Назовем такую операцию ''операцией релаксации''. После того, как релаксация будет выполнена для всех предков вершины <tex>u</tex>, можно будет считать, что <tex>u.num</tex> содержит актуальные данные.  
+
Для каждой вершины <tex>u</tex> дерева палиндромов будем хранить число вхождений строки <tex>u'</tex> в исходную строку (не обязательно актуальные данные) и число, которое необходимо добавить к числу вхождений всех потомков <tex>v</tex> вершины <tex>u</tex>. Назовем такую операцию добавления ''операцией релаксации''. После того, как релаксация будет выполнена для всех предков вершины <tex>u</tex>, можно будет считать, что посчитанное число вхождений соответствует действительности.  
 +
 
 
Данный метод очень похож на метод, описанный в статье [[Несогласованные_поддеревья._Реализация_массового_обновления|про реализацию массовых обновлений в деревьях отрезков]].
 
Данный метод очень похож на метод, описанный в статье [[Несогласованные_поддеревья._Реализация_массового_обновления|про реализацию массовых обновлений в деревьях отрезков]].
  
Строка 136: Строка 124:
 
Для решения данной задачи применим тот же алгоритм, что и в прошлой задаче, а затем пройдем по всем вершинам дерева палиндромов и выберем подходящую.
 
Для решения данной задачи применим тот же алгоритм, что и в прошлой задаче, а затем пройдем по всем вершинам дерева палиндромов и выберем подходящую.
  
==Примечания==
+
== См. также ==
 +
* [[Алгоритм Манакера]]
 +
* [[Сжатое суффиксное дерево]]
 +
* [[Суффиксный массив]]
 +
 
 +
== Примечания ==
 
<references/>
 
<references/>
  
 
== Источники информации ==
 
== Источники информации ==
* [http://adilet.org/blog/25-09-14/ http://adilet.org/ {{---}} Palindromic tree {{---}} Adilet ADJA Zhaxybay]
+
* [http://adilet.org/blog/25-09-14/ Adilet.org {{---}} Palindromic tree, Adilet ADJA Zhaxybay]
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]

Текущая версия на 19:03, 4 сентября 2022

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

Эту структуру данных придумал Михаил Рубинчик[1] и рассказал её на летних сборах в Петрозаводске в 2014 году. Наиболее подробное о дереве палиндромов или овердреве (palindromic tree, eertree) можно прочитать в диссертации Михаил Рубинчика [1]

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

Дерево палиндромов состоит из вершин, каждая из которых соответствует палиндрому. Все вершины соответствуют разным палиндромам. Через [math]u'[/math] будем обозначать строку, которой соответствует вершина [math]u[/math]. Рёбра дерева палиндромов ориентированные и помечены символами. Ребро с символом [math]x[/math] ведет из вершины [math]u[/math] в вершину [math]v[/math] тогда и только тогда, когда [math]v'=xu'x[/math].

Пример четырех вершин дерева палиндромов В данном примере мы получаем палиндром aba добавлением символа a к обоим сторонам палиндрома b


Стоит обратить внимание на то, что название структуры данных выбрано не совсем удачно. На самом деле структура представляет из себя два дерева — одно для палиндромов чётной длины, другое для палиндромов нечётной длины. Обозначим корни этих деревьев за [math]root_{even}[/math] и [math]root_{odd}[/math] соответственно.

Помимо вершин и рёбер в дереве палиндромов также присутствуют суффиксные ссылки. Для каждой вершины [math]u[/math] её суффиксная ссылка ведет в такую вершину [math]w[/math], что [math]w'[/math] является наибольшим суффиксом строки [math]u'[/math] относительно других вершин. При этом важно понимать, что суффиксная ссылка из вершины одного дерева может вести как в то же, так и в другое дерево.

Мы добавили суффиксную ссылку (пунктирная линия) из aba к a потому, что a является наибольшим паллиндромом-суффиксом строки aba


При реализации в целях экономии памяти мы не будем хранить для каждой вершины соответствующую ей строку-палиндром. Этот подход был бы неэффективным с точки зрения памяти. Вместо этого мы будем хранить только длину палиндрома (и для некоторых задач позицию палиндрома в строке).

Итак, структура будет состоять из двух деревьев и, соответственно, двух корней. Для удобства реализации каждый корень будет соответствовать фиктивной строке.

  • [math]root_{odd}[/math] будет соответствовать палиндрому длины [math]-1[/math]. Это нужно для того, чтобы не обрабатывать отдельно случай добавления палиндрома длины [math]1[/math]. Теперь каждый раз при добавлении ребра из вершины [math]u[/math] к вершине [math]v[/math], мы будем просто считать что [math]|v'|=|u'| + 2[/math].
  • [math]root_{even}[/math] будет соответствовать фиктивному палиндрому длины [math]0[/math].

Суффиксные ссылки обоих корней будут вести к вершине [math]root_{odd}[/math]. Это соглашение нужно также для удобства реализации — теперь каждая вершина имеет суффиксную ссылку.

Построение

Опишем далее по шагам процесс построения дерева палиндромов для данной строки. Изначально оно состоит из двух фиктивных вершин, а далее будет достраиваться инкрементально после каждого рассмотренного символа строки.

Будем обрабатывать строку символ за символом. Пусть мы уже обработали некоторый префикс [math]p[/math] и теперь хотим добавить следующий символ строки, назовем его [math]x[/math]. Palindrome tree build1.png
Будем также поддерживать максимальный палиндром-суффикс обработанного префикса [math]p[/math]. Назовем его [math]t[/math]. Palindromic tree nodes.png
Т.к. [math]t[/math] находится в уже обработанной части строки, то ему соответствует какая-то вершина в дереве. У этой вершины есть суффиксная ссылка на какую-то другую вершину, у которой тоже есть суффиксная ссылка и т.д. Цепочка суффиксных ссылок из t
Найдем теперь палиндром-суффикс строки [math]px[/math] (т.е. нового префикса). Искомая строка будет иметь вид [math]xAx[/math], где [math]A[/math] — какая-то строка, возможно пустая (или фиктивная строка длины [math]-1[/math], соответствующая корню [math]root_{odd}[/math], если искомый палиндром-суффикс — это просто символ [math]x[/math]).

Т.к. [math]xAx[/math] — палиндром, то [math]A[/math] — тоже палиндром, и, более того, это суффикс строки [math]p[/math]. Поэтому он может быть достигнут из [math]t[/math] по суффиксным ссылкам.

Palindrome tree build4.png


Утверждение (1):
Строка [math]xAx[/math] — это единственная подстрока-палиндром строки [math]px[/math], которой, возможно, нет в [math]p[/math] (т.е. все другие подстроки-палиндромы есть).
[math]\triangleright[/math]
Заметим, что все новые подстроки-палиндромы, которых не было в [math]p[/math], должны оканчиваться на символ [math]x[/math], и поэтому должны быть палиндромом-суффиксом строки [math]px[/math]. Из-за того, что [math]xAx[/math] — наибольший палиндром-суффикс строки [math]px[/math], все остальные меньшие палиндромы-суффиксы этой строки уже есть в каком-то префиксе строки [math]xAx[/math] (т.к. для каждого суффикса палиндрома есть равный ему префикс) и, соответственно, уже есть в [math]p[/math].
[math]\triangleleft[/math]

Таким образом, чтобы обработать очередной символ [math]x[/math], нужно просто спуститься по суффиксным ссылкам вершины [math]t[/math] до тех пор, пока мы не найдем подходящую строку [math]A[/math] (причем мы всегда можем найти такую строку, возможно длины [math]-1[/math], если очередная суффиксная ссылка будет вести в корень). Затем нужно проверить, есть ли уже ребро по символу [math]x[/math] из вершины, соответствующей [math]A[/math], и если нет, добавить это ребро в новую вершину [math]xAx[/math].

Теперь нужно добавить суффиксную ссылку из вершины [math]xAx[/math]. Если эта вершина уже существовала до добавления символа [math]x[/math], ничего делать не нужно — суффиксная ссылка и так указывает на правильную вершину. Иначе нужно найти наибольший палиндром-суффикс строки [math]xAx[/math], который будет иметь вид [math]xBx[/math], где [math]B[/math] — это некоторая строка, возможно, пустая. Следуя той же логике, которую мы использовали раньше, [math]B[/math] — это палиндром-суффикс строки [math]p[/math] и может быть достигнут из [math]t[/math] по суффиксным ссылкам.


Утверждение (2):
Очередная добавленная вершина [math]u[/math] не может быть максимальным палиндромом-суффиксом какой-либо ранее добавленной вершины [math]v[/math]
[math]\triangleright[/math]
Предположим, что это не так. Тогда оказывается, что не все подпалиндромы строки [math]v'[/math] были добавлены в дерево палиндромов ранее. А это противоречит утверждению 1.
[math]\triangleleft[/math]

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

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

Память

Каждая вершина в дереве соответствует подпалиндрому, всего различных подпалиндромов в строке не более [math]n[/math] (т.к. при добавлении очередного символа появляется не более одного нового палиндрома). Поэтому дерево палиндромов занимает [math]O(n)[/math] памяти.

Время

Чтобы оценить временную сложность алгоритма, нужно заметить, что по мере того, как мы обрабатываем строку символ за символом, левая граница наибольшего палиндрома-суффикса уже обработанной строки сдвигается только вправо. Очевидно, эта граница может двигаться вправо не более [math]n[/math], где [math]n[/math] — длина строки, для которой мы строим дерево. То же самое относится и к левой границе той строки, на которую ведет суффиксная ссылка вновь добавленной вершины.

Таким образом, суммарное время работы построения алгоритма [math]O(n)[/math].

Применения

Число новых палиндромов, порождаемых очередным символом

Задача:
Необходимо определить число подпалиндромов, которые будут новыми после добавления символа [math]x[/math] в конец строки [math]s[/math].


Например, при добавлении символа [math]a[/math] к строке [math]aba[/math], которая уже состоит из палиндромов [math]a[/math], [math]b[/math] и [math]aba[/math], добавляется новый палиндром [math]aa[/math].

Мы знаем, что число новых подпалиндромов при добавлении символа [math]0[/math] или [math]1[/math]. Так что решение задачи довольно простое — будем строить дерево палиндромов символ за символом и для каждого нового символа отвечать, был ли добавлен новый палиндром или нет (определить это можно, например, по тому, были ли добавлены новые вершины к структуре).


Также данную структуру можно использовать для подсчета числа различных подпалиндромов строки. Это будет просто число вершин.

Число подпалиндромов

Задача:
Требуется определить число подпалиндромов, которые содержатся в данной строке.


Например, строка [math]aba[/math] имеет четыре подпалиндрома: дважды [math]a[/math], [math]b[/math] и [math]aba[/math].

Для решения задачи будем строить дерево палиндромов для данной строки и на каждом шаге добавлять к ответу все палиндромы, которые содержат этот новый символ.

Рассмотрим очередной шаг алгоритма после добавления символа [math]x[/math]. Обозначим за [math]t[/math] вершину, соответствующую максимальному палиндрому-суффиксу, содержащую этот последний символ. Заметим, что новые палиндромы, которые добавляет [math]x[/math] — это [math]t'[/math], а также все палиндромы, достижимые из [math]t[/math] по суффиксным ссылкам (т.к. только они содержат новый символ [math]x[/math]). Для того чтобы быстро найти их число, будем хранить в каждой вершине длину цепочки суффиксных ссылок до корня (включая саму вершину), а затем будем просто прибавлять к ответу это число для каждого очередного [math]t[/math] по мере добавления новых символов.


Эта задача также может быть решена алгоритмом Манакера за ту же асимптотику, однако данный алгоритм не может быть расширен для более широкого класса задач, в отличие от дерева палиндромов.

Число вхождений каждого подпалиндрома в строку

Задача:
Необходимо найти число вхождений каждого подпалиндрома строки в неё саму.


Чтобы решить эту задачу деревом палиндромов, нужно обратить внимание на то, что при добавлении нового символа увеличивается количество вхождений наибольшего палиндрома-суффикса [math]t[/math], содержащего новый символ, и всех палиндромов, достижимых из [math]t[/math] по суффиксным ссылкам.

Для каждой вершины [math]u[/math] дерева палиндромов будем хранить число вхождений строки [math]u'[/math] в исходную строку (не обязательно актуальные данные) и число, которое необходимо добавить к числу вхождений всех потомков [math]v[/math] вершины [math]u[/math]. Назовем такую операцию добавления операцией релаксации. После того, как релаксация будет выполнена для всех предков вершины [math]u[/math], можно будет считать, что посчитанное число вхождений соответствует действительности.

Данный метод очень похож на метод, описанный в статье про реализацию массовых обновлений в деревьях отрезков.

Поиск рефрен-палиндрома

Задача:
Для данной строки необходимо найти палиндром, произведение длины которого на количество вхождений в строку является максимальным.


Для решения данной задачи применим тот же алгоритм, что и в прошлой задаче, а затем пройдем по всем вершинам дерева палиндромов и выберем подходящую.

См. также

Примечания

Источники информации