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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание структуры)
(Построение)
(не показаны 34 промежуточные версии 5 участников)
Строка 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>.
[[Основные_определения_теории_графов#def_graph_edge_1|Ребра]] дерева палиндромов ориентированные и помечены символами. Ребро с символом <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>root_{even}</tex> и <tex>root_{odd}</tex> соответственно.
+
Стоит обратить внимание на то, что название структуры данных выбрано не совсем удачно. На самом деле структура представляет из себя два дерева {{---}} одно для палиндромов чётной длины, другое для палиндромов нечётной длины. Обозначим корни этих деревьев за <tex>root_{even}</tex> и <tex>root_{odd}</tex> соответственно.
  
Помимо вершин и ребер в дереве палиндромов также присутствуют ''суффиксные ссылки''. Для каждой вершины <tex>u</tex> ее суффиксная ссылка ведет в такую вершину <tex>w</tex>, что <tex>w'</tex> является наибольшим суффиксом строки <tex>u'</tex> относительно других вершин. При этом важно понимать, что суффиксная ссылка из вершины одного дерева может вести как в то же, так и в другое дерево.
+
Помимо вершин и рёбер в дереве палиндромов также присутствуют ''суффиксные ссылки''. Для каждой вершины <tex>u</tex> её суффиксная ссылка ведет в такую вершину <tex>w</tex>, что <tex>w'</tex> является наибольшим суффиксом строки <tex>u'</tex> относительно других вершин. При этом важно понимать, что суффиксная ссылка из вершины одного дерева может вести как в то же, так и в другое дерево.
  
 
[[Файл:palindrome_tree_suffix_link.png|Мы добавили суффиксную ссылку (пунктирная линия) из aba к a потому, что a является наибольшим паллиндромом-суффиксом строки aba|border]]
 
[[Файл:palindrome_tree_suffix_link.png|Мы добавили суффиксную ссылку (пунктирная линия) из aba к a потому, что a является наибольшим паллиндромом-суффиксом строки aba|border]]
Строка 20: Строка 20:
  
 
Итак, структура будет состоять из двух деревьев и, соответственно, двух корней. Для удобства реализации каждый корень будет соответствовать фиктивной строке.
 
Итак, структура будет состоять из двух деревьев и, соответственно, двух корней. Для удобства реализации каждый корень будет соответствовать фиктивной строке.
* <tex>root_{odd}</tex> будет соответствовать палиндрому длины <tex>-1</tex>. Это нужно для того, чтобы не обрабатывать отдельно случай добавления палиндрома длины 1. Теперь каждый раз при добавлении новой вершины <tex>u</tex> к вершине <tex>v</tex> мы будем просто указывать ее длину равной <tex>u.len = v.len + 2</tex>.
+
* <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> будет соответствовать фиктивному палиндрому длины 0.
+
* <tex>root_{even}</tex> будет соответствовать фиктивному палиндрому длины <tex>0</tex>.
  
Суффиксные ссылки обоих корней будут вести к вершине <tex>root_{odd}</tex>.
+
Суффиксные ссылки обоих корней будут вести к вершине <tex>root_{odd}</tex>. Это соглашение нужно также для удобства реализации {{---}} теперь каждая вершина имеет суффиксную ссылку.
  
 
== Построение ==
 
== Построение ==
{| border="1"
+
Опишем далее по шагам процесс построения дерева палиндромов для данной строки. Изначально оно состоит из двух фиктивных вершин, а далее будет достраиваться инкрементально после каждого рассмотренного символа строки.
 +
 
 +
{| style="background-color:#CCC;margin:0.5px"
 
  |-
 
  |-
  |Будем обрабатывать строку символ за символом. Пусть мы уже обработали некоторый префикс <tex>p</tex> и теперь хотим добавить следующий символ строки, назовем его <tex>x</tex>.
+
  |style="background-color:#FFF;padding:2px 30px"|Будем обрабатывать строку символ за символом. Пусть мы уже обработали некоторый префикс <tex>p</tex> и теперь хотим добавить следующий символ строки, назовем его <tex>x</tex>.
  |[[Файл:palindrome_tree_build1.png|500px|border]]
+
  |style="background-color:#FFF;padding:2px 30px"|[[Файл:palindrome_tree_build1.png|500px]]
 
  |-
 
  |-
  |Будем также поддерживать максимальный палиндром-суффикс обработанного префикса <tex>p</tex>. Назовем его <tex>t</tex>.
+
  |style="background-color:#FFF;padding:2px 30px"|Будем также поддерживать максимальный палиндром-суффикс обработанного префикса <tex>p</tex>. Назовем его <tex>t</tex>.
  |[[Файл:palindromic_tree_nodes.png|500px|border]]
+
  |style="background-color:#FFF;padding:2px 30px"|[[Файл:palindromic_tree_nodes.png|500px]]
 
  |-
 
  |-
  |Т.к. <tex>t</tex> находится в уже обработанной части строки, то ему соответствует какая-то вершина в дереве. У этой вершины есть суффиксная ссылка на какую-то другую вершину, у которой тоже есть суффиксная ссылка и т.д.
+
  |style="background-color:#FFF;padding:2px 30px"|Т.к. <tex>t</tex> находится в уже обработанной части строки, то ему соответствует какая-то вершина в дереве. У этой вершины есть суффиксная ссылка на какую-то другую вершину, у которой тоже есть суффиксная ссылка и т.д.
  |[[Файл:palindrome_tree_build3.png|500px|Цепочка суффиксных ссылок из t|border]]
+
  |style="background-color:#FFF;padding:2px 30px"|[[Файл:palindrome_tree_build3.png|500px|Цепочка суффиксных ссылок из t]]
 
  |-
 
  |-
  |Найдем теперь палиндром-суффикс строки <tex>px</tex> (т.е. нового префикса). Искомая строка будет иметь вид <tex>xAx</tex>, где <tex>A</tex> {{---}} какая-то строка, возможно пустая (или фиктивная строка длины <tex>-1</tex>, соответствующая корню <tex>root_{odd}</tex>, если искомый палиндром-суффикс {{---}} это просто символ <tex>x</tex>).  
+
  |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> по суффиксным ссылкам.
 
Т.к. <tex>xAx</tex> {{---}} палиндром, то <tex>A</tex> {{---}} тоже палиндром, и, более того, это суффикс строки <tex>p</tex>. Поэтому он может быть достигнут из <tex>t</tex> по суффиксным ссылкам.
  |[[Файл:palindrome_tree_build4.png|500px|border]]
+
  |style="background-color:#FFF;padding:2px 30px"|[[Файл:palindrome_tree_build4.png|500px]]
 
  |}
 
  |}
  
  
 
{{Утверждение
 
{{Утверждение
 +
|author=1
 
|statement=
 
|statement=
Строка <tex>xAx</tex> {{---}} это единственная подстрока-палиндром строки <tex>p+x</tex>, которой, возможно, нет в <tex>p</tex> (т.е. все другие подстроки-палиндромы есть).  
+
Строка <tex>xAx</tex> {{---}} это единственная подстрока-палиндром строки <tex>px</tex>, которой, возможно, нет в <tex>p</tex> (т.е. все другие подстроки-палиндромы есть).  
 
|proof=  
 
|proof=  
Заметим, что все новые подстроки-палиндромы, которых не было в <tex>p</tex>, должны оканчиваться на символ <tex>x</tex>, и поэтому должны быть палиндромом-суффиксом строки <tex>p+x</tex>. Из-за того, что <tex>xAx</tex> {{---}} наибольший палиндром-суффикс строки <tex>p+x</tex>, все остальные меньшие палиндромы-суффиксы этой строки уже есть в каком-то префиксе строки <tex>xAx</tex> (т.к. для каждого суффикса палиндрома есть равный ему префикс) и, соответственно, уже есть в <tex>p</tex>.}}
+
Заметим, что все новые подстроки-палиндромы, которых не было в <tex>p</tex>, должны оканчиваться на символ <tex>x</tex>, и поэтому должны быть палиндромом-суффиксом строки <tex>px</tex>. Из-за того, что <tex>xAx</tex> {{---}} наибольший палиндром-суффикс строки <tex>px</tex>, все остальные меньшие палиндромы-суффиксы этой строки уже есть в каком-то префиксе строки <tex>xAx</tex> (т.к. для каждого суффикса палиндрома есть равный ему префикс) и, соответственно, уже есть в <tex>p</tex>.}}
 +
 
 +
Таким образом, чтобы обработать очередной символ <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>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> по суффиксным ссылкам.
+
{{Утверждение
 +
|author=2
 +
|statement=
 +
Очередная добавленная вершина <tex>u</tex> не может быть максимальным палиндромом-суффиксом какой-либо ранее добавленной вершины <tex>v</tex>
 +
|proof=
 +
Предположим, что это не так. Тогда оказывается, что не все подпалиндромы строки <tex>v'</tex> были добавлены в дерево палиндромов ранее. А это противоречит утверждению 1.
 +
}}
 +
 
 +
Таким образом, добавление очередного символа по описанному алгоритму происходит корректно.
  
 
== Оценка сложности ==
 
== Оценка сложности ==
Строка 64: Строка 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;
 
    suff_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(suff_link[last])][c];
 
        to[last][c] = sz++;
 
    }
 
    last = to[last][c];
 
}
 
 
Чтобы построить дерево палиндромов, нужно просто для каждого символа исходной строки последовательно вызвать <tex>\mathrm{add\_letter}</tex>.
 
  
 
== Применения ==
 
== Применения ==
Строка 108: Строка 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> по мере добавления новых символов.  
 +
 
  
 
Эта задача также может быть решена [[Алгоритм_Манакера|алгоритмом Манакера]] за ту же асимптотику, однако данный алгоритм не может быть расширен для более широкого класса задач, в отличие от дерева палиндромов.
 
Эта задача также может быть решена [[Алгоритм_Манакера|алгоритмом Манакера]] за ту же асимптотику, однако данный алгоритм не может быть расширен для более широкого класса задач, в отличие от дерева палиндромов.
Строка 128: Строка 109:
 
{{Задача
 
{{Задача
 
|definition=
 
|definition=
Необходимо найти число вхождений каждого подпалиндрома строки в нее саму.}}
+
Необходимо найти число вхождений каждого подпалиндрома строки в неё саму.}}
  
 
Чтобы решить эту задачу деревом палиндромов, нужно обратить внимание на то, что при добавлении нового символа увеличивается количество вхождений наибольшего палиндрома-суффикса <tex>t</tex>, содержащего новый символ, и всех палиндромов, достижимых из <tex>t</tex> по суффиксным ссылкам.
 
Чтобы решить эту задачу деревом палиндромов, нужно обратить внимание на то, что при добавлении нового символа увеличивается количество вхождений наибольшего палиндрома-суффикса <tex>t</tex>, содержащего новый символ, и всех палиндромов, достижимых из <tex>t</tex> по суффиксным ссылкам.
Строка 142: Строка 123:
  
 
Для решения данной задачи применим тот же алгоритм, что и в прошлой задаче, а затем пройдем по всем вершинам дерева палиндромов и выберем подходящую.
 
Для решения данной задачи применим тот же алгоритм, что и в прошлой задаче, а затем пройдем по всем вершинам дерева палиндромов и выберем подходящую.
 
== Примечания ==
 
<references/>
 
  
 
== См. также ==
 
== См. также ==
Строка 150: Строка 128:
 
* [[Сжатое суффиксное дерево]]
 
* [[Сжатое суффиксное дерево]]
 
* [[Суффиксный массив]]
 
* [[Суффиксный массив]]
 +
 +
== Примечания ==
 +
<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]
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]

Версия 10:21, 9 ноября 2020

Дерево палиндромов (англ. 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], можно будет считать, что посчитанное число вхождений соответствует действительности.

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

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

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


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

См. также

Примечания

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