Дерево палиндромов ( англ. palindromic tree , также овердрево , англ. eertree ) — структура данных , предназначенная для хранения и обработки палиндромных подстрок некоторой строки . Была предложена учёными из Уральского федерального университета Михаилом Рубинчиком и Арсением Шуром в 2015 году. Представляет собой два префиксных дерева , собранных из правых «половинок» палиндромных подстрок чётной и нечётной длины соответственно. Структура занимает ${\displaystyle O(n)}$ памяти и может быть построена за время ${\displaystyle O(n\log \sigma )}$ , где ${\displaystyle n}$ — длина строки, а ${\displaystyle \sigma }$ — количество различных символов в ней. С помощью дерева палиндромов можно эффективно решать такие задачи, как подсчёт числа различных палиндромных подстрок, поиск разбиения строки на наименьшее число палиндромов, проверка подстроки на то, является ли она палиндромом, и другие.

Обозначения

Пусть ${\displaystyle S=s_{1}s_{2}\dots s_{n}}$ — некоторая строка, а ${\displaystyle S^{R}=s_{n}s_{n-1}\dots s_{1}}$ — обращённая строка ${\displaystyle S}$ . При описании дерева палиндромов строки ${\displaystyle S}$ используются следующие обозначения :

• Строка ${\displaystyle S}$ называется палиндромом , если она читается одинаково слева направо и справа налево, то есть если ${\displaystyle S=S^{R}}$ .

• Подстрокой называют непрерывную подпоследовательность строки ${\displaystyle S}$ и обозначают ${\displaystyle S_{l,r}=s_{l}s_{l+1}\dots s_{r}}$ .

• В частности, подстрока, у которой ${\displaystyle l=1}$ , называется префиксом строки ${\displaystyle S}$ , а подстрока, у которой ${\displaystyle r=n}$ , — суффиксом строки ${\displaystyle S}$ .

• Палиндромной подстрокой ( подпалиндромом ) называют подстроку ${\displaystyle S}$ , которая является палиндромом. Если эта подстрока также является префиксом или суффиксом строки ${\displaystyle S}$ , то её называют префикс- или суффикс-палиндромом соответственно.

• Префиксным деревом называют корневое ориентированное дерево , дуги которого помечены символами таким образом, что из любой вершины ${\displaystyle v}$ этого дерева исходит не больше одной дуги , помеченной данным символом.

• Каждой вершине префиксного дерева соответствует строка, равная конкатенации символов на пути из корня дерева в эту вершину.

Структура дерева

В обозначениях выше, дерево палиндромов строки ${\displaystyle S}$ — это ориентированный граф , каждая вершина которого соответствует некоторому уникальному подпалиндрому строки и отождествляется с ним. Если у строки есть подпалиндромы ${\displaystyle t}$ и ${\displaystyle ctc}$ , где ${\displaystyle c}$ — некоторый символ , то в дереве палиндромов есть дуга , помеченная символом ${\displaystyle c}$ , из вершины, соответствующей ${\displaystyle t}$ , в вершину, соответствующую ${\displaystyle ctc}$ . В таком графе у любой вершины может быть только одна входящая дуга. Для удобства также вводятся две служебные вершины, которые соответствуют палиндромам длины ${\displaystyle 0}$ ( пустая строка ) и ${\displaystyle -1}$ («мнимая» строка) соответственно. Дуги из пустой строки ведут в вершины, соответствующие палиндромам вида ${\displaystyle cc}$ , а из «мнимой строки» — в вершины, соответствующие палиндромам вида ${\displaystyle c}$ (то есть состоящим из единственного символа). Вершина называется чётной , если ей соответствует палиндром чётной длины, и нечётной в противном случае. Из определения следует, что дуги в дереве палиндромов проходят только между вершинами с одинаковой чётностью. С точки зрения префиксных деревьев данная структура может быть описана следующим образом :

Вершины и дуги дерева палиндромов образуют два префиксных дерева, корни которых находятся в вершинах, задающих пустую и «мнимую» строки соответственно. При этом первое префиксное дерево составлено из правых половин подпалиндромов чётной длины, а второе — нечётной.

Количество вершин в дереве палиндромов не превосходит ${\displaystyle n+2}$ , что является прямым следствием следующей леммы :

У строки ${\displaystyle S}$ длины ${\displaystyle n}$ может быть не больше ${\displaystyle n}$ различных непустых палиндромных подстрок. Более того, после приписывания некоторого символа ${\displaystyle c}$ в конец строки количество различных подпалиндромов данной строки может увеличиться не больше, чем на ${\displaystyle 1}$ .

Помимо обычных дуг, которые служат переходами для префиксного дерева, для каждой вершины дерева палиндромов определяется суффиксная ссылка , которая ведёт из вершины ${\displaystyle v}$ в вершину ${\displaystyle u}$ , соответствующую наибольшему собственному (не равному всей строке ${\displaystyle v}$ ) суффикс-палиндрому ${\displaystyle v}$ . При этом суффиксная ссылка из «мнимой» вершины не определена, а из пустой вершины по определению ведёт в «мнимую». Суффиксные ссылки образуют дерево с корнем в «мнимой» вершине и играют важную роль в построении дерева палиндромов .

Построение

Как и многие другие строковые структуры, дерево палиндромов строится итеративно . Изначально оно состоит лишь из вершин, соответствующих пустой и мнимой строкам. Затем структура постепенно перестраивается при наращивании строки по одному символу. Так как при добавлении одного символа в строке появляется не более одного нового палиндрома, перестройка дерева в худшем случае потребует добавления одной новой вершины и суффиксной ссылки к ней. Для определения возможной новой вершины в ходе построения дерева поддерживается указатель last на вершину, соответствующую наибольшему из текущих суффикс-палиндромов .

Все суффикс-палиндромы строки достижимы по суффиксным ссылкам из last , поэтому для определения нового суффикс-палиндрома (именно он будет соответствовать новой вершине, если таковая появится) необходимо переходить по суффиксным ссылкам last , пока не обнаружится, что символ, предшествующий текущему суффикс-палиндрому, совпадает с символом, который был приписан к строке. Более формально, пусть ${\displaystyle P}$ — максимальный суффикс-палиндром строки ${\displaystyle S_{1,k}=s_{1}s_{2}\dots s_{k}}$ , тогда либо ${\displaystyle P=s_{k}}$ , либо ${\displaystyle P=s_{k}Qs_{k}}$ , где ${\displaystyle Q}$ — некоторый суффикс-палиндром ${\displaystyle S_{1,k-1}}$ . Таким образом, перебирая ${\displaystyle Q}$ среди суффиксных ссылок last , можно определить, может ли он быть расширен до ${\displaystyle P}$ путём сравнения символов ${\displaystyle s_{k-|Q|-1}}$ и ${\displaystyle s_{k}}$ . Когда соответствующий суффикс-палиндром ${\displaystyle Q}$ был найден, следует проверить, присутствует ли в дереве палиндромов переход из соответствующей ему вершины по символу ${\displaystyle s_{k}}$ .

Если такой переход есть, то ${\displaystyle P}$ уже встречался в строке ранее и соответствует вершине, в которую ведёт этот переход. В противном случае необходимо создать для него новую вершину и провести переход по ${\displaystyle s_{k}}$ из ${\displaystyle Q}$ . Затем следует определить суффиксную ссылку для ${\displaystyle P}$ , которая соответствует второму максимальному суффикс-палиндрому ${\displaystyle S_{1,k}}$ . Для того, чтобы её найти, следует продолжать обход суффиксных ссылок last , пока не встретится вторая вершина ${\displaystyle Q}$ , такая что ${\displaystyle s_{k-|Q|-1}=s_{k}}$ ; именно эта вершина и будет суффиксный ссылкой ${\displaystyle P}$ . Если обозначить переход из вершины ${\displaystyle v}$ по символу ${\displaystyle c}$ как ${\displaystyle \delta (v,c)}$ , весь процесс может быть описан следующим псевдокодом :

функция find_link(v):
    пока sk-len(v)-1 ≠ sk:
        присвоить v = link(v)
    вернуть v

функция add_letter(c):
    присвоить k = k + 1
    определить sk = c
    определить q = find_link(last)
    если δ(q, c) не определено:
        определить p = new_vertex()
        определить len(p) = len(q) + 2
        определить link(p) = δ(find_link(link(q)), c)
        определить δ(q, c) = p
    присвоить last = δ(q, c)

Здесь предполагается, что изначально дерево описывается лишь двумя вершинами с длинами ${\displaystyle 0}$ и ${\displaystyle -1}$ соответственно с суффиксной ссылкой из первой вершины во вторую. В переменной last хранится вершина, соответствующая наибольшему суффикс-палиндрому текущей строки, изначально она указывает на вершину нулевой строки. Также предполагается, что ${\displaystyle k}$ изначально равно ${\displaystyle 0}$ и в ${\displaystyle s_{0}}$ записан некоторый служебный символ, который не встречается в строке ${\displaystyle s_{1}s_{2}\dots s_{k}}$ .

Вычислительная сложность

Сложность алгоритма может варьировать в зависимости от структур данных, в которых хранится таблица переходов в дереве. В общем случае при использовании ассоциативного массива время, затрачиваемое на обращение к ${\displaystyle \delta (q,c)}$ , достигает ${\displaystyle O(\log \sigma )}$ , где ${\displaystyle \sigma }$ — размер алфавита, из символов которого построена строка. Стоит заметить, что каждая итерация первого вызова find_link уменьшает длину last , а второго — длину link(last) , которые между последовательными вызовам add_letter могут увеличиться только на единицу. Таким образом, суммарное время работы find_link не превосходит ${\displaystyle O(n)}$ , а общее время, требуемое для выполнения ${\displaystyle n}$ вызовов add_letter , можно оценить как ${\displaystyle O(n\log \sigma )}$ . Расход памяти у данной структуры в худшем случае линейный, однако если рассматривать усреднённый размер структуры по всем строкам заданной длины ${\displaystyle n}$ , средний расход памяти будет порядка ${\displaystyle O({\sqrt {n\sigma }})}$ .

Модификации

Одновременно с введением данной структуры данных Рубинчик и Шур также предложили ряд модификаций, позволяющих расширить область задач, решаемых деревом палиндромов. В частности, был предложен метод, позволяющий с той же асимптотикой построить общее дерево палиндромов для множества строк ${\displaystyle S_{1},S_{2},\dots ,S_{k}}$ . Такая модификация позволяет решать те же задачи, рассматриваемые в контексте множества строк — например, найти наибольший общий подпалиндром всех строк или число различных подпалиндромов всех строк в совокупности. Другой предложенной модификацией стал вариант построения дерева, при котором на добавление одного символа требуется ${\displaystyle O(\log n)}$ времени в худшем случае (а не ${\displaystyle O(\log \sigma )}$ амортизированно , как это происходит в стандартном построении) и ${\displaystyle O(1)}$ памяти. Такой подход позволяет обеспечить дерева, при которой можно в произвольные моменты времени откатывать добавление последнего символа. Кроме того, была предложена полностью персистентная версия дерева, позволяющая обратиться и дописать символ к любой из сохранённых ранее версий за ${\displaystyle O(\log n)}$ времени и памяти в худшем случае .

В 2019 году Ватанабе с коллегами разработали на основе дерева палиндромов структуру данных, называемую e ² rtre ² , для работы с подпалиндромами строк, заданных кодированием длин серий , а в 2020 году тот же состав авторов, совместно с Миено, разработали два алгоритма, позволяющих поддерживать дерево палиндромов на скользящем окне размера ${\displaystyle d}$ . Первый из указанных алгоритмов требует ${\displaystyle O(n\log \sigma )}$ времени и ${\displaystyle O(d)}$ памяти, а второй — ${\displaystyle O(n+d\sigma )}$ времени и ${\displaystyle O(d\sigma )}$ памяти .

Применения

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

Одной из задач, для которых была разработана данная структура, является подсчёт различных подпалиндромов в строке . Она может быть поставлена следующим образом: к изначально пустой строке поочерёдно приписывается по одному символу. На каждом шаге необходимо вывести число различных подпалиндромов в данной строке. С точки зрения дерева палиндромов это эквивалентно тому, чтобы на каждом шаге вывести количество нетривиальных вершин в структуре. Линейное решение для оффлайн-версии данной задачи было представлено в 2010 году , а оптимальное решение со временем исполнения ${\displaystyle O(n\log \sigma )}$ для онлайн-версии было найдено в 2013 году . Указанное решение, однако, использовало две «тяжеловесные» структуры данных — аналог алгоритма Манакера , а также суффиксное дерево . Дерево палиндромов же, с одной стороны, имеет ту же асимптотику в худшем случае, а с другой — является значительно более легковесной структурой .

Другим возможным применением данной структуры является перечисление палиндромно-богатых двоичных строк . Ранее было показано, что слово длины ${\displaystyle n}$ может содержать не более ${\displaystyle n+1}$ различных палиндромов, палиндромно-богатыми называются слова, на которых данная оценка достигается. Понятие палиндромно-богатых слов было введено Эми Глен и коллегами в 2008 году . Рубинчик и Шур показали, что с помощью дерева палиндромов можно обнаружить все палиндромно-богатые слова, чья длина не превосходит ${\displaystyle n}$ за ${\displaystyle O(R)}$ , где ${\displaystyle R}$ — количество таких слов. Данный результат позволил увеличить количество известных членов последовательности в OEIS c 25 до 60. Полученные данные показали, что последовательность растёт значительно медленнее, чем это предполагалось ранее, а именно она ограничена сверху как ${\displaystyle O(1,605^{n})}$ .

Примечания

Литература

Ссылки

• (неопр.) . Вики-конспекты ИТМО .