Дерево палиндромов

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

Обозначения

Пусть [math]\displaystyle{ S=s_1 s_2 \dots s_n }[/math] — некоторая строка, а [math]\displaystyle{ S^R = s_n s_{n-1} \dots s_1 }[/math] — обращённая строка [math]\displaystyle{ S }[/math]. При описании дерева палиндромов строки [math]\displaystyle{ S }[/math] используются следующие обозначения<ref>Шаблон:Sfn-текст</ref>:

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

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

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

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

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

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

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

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

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

Сложность алгоритма может варьировать в зависимости от структур данных, в которых хранится таблица переходов в дереве.

Применения

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