Дерево палиндромов (Eertree): Новое слово в алгоритмах на строках

В отличие от суффиксного дерева или бора (Trie), структура Eertree (слово Tree, записанное наоборот с добавлением Tree) строится на специфических математических свойствах палиндромов. Доказано, что любая строка длины N физически не может содержать более N уникальных палиндромных подстрок. Именно поэтому Дерево палиндромов занимает строго линейный объем памяти O(N).

Структура Eertree состоит из графа узлов, где каждый узел представляет уникальный палиндром. Дерево имеет два корня:

1. Корень для палиндромов четной длины (виртуальная строка длины 0).
2. Корень для палиндромов нечетной длины (виртуальная строка длины -1).

Направленные прямые ребра (переходы) между узлами означают операцию добавления одного и того же символа по краям. Например, переход по букве "К" от узла "АБ_БА" ведет к узлу "КАБ_БАК".
Ключевая магия структуры — это суффиксные ссылки (Suffix Links). Каждая вершина имеет ровно одну суффиксную ссылку, которая указывает на самый длинный палиндром, являющийся собственным суффиксом данного палиндрома. Эти ссылки позволяют алгоритму мгновенно "откатываться" при чтении нового символа текста, находя максимальное симметричное совпадение.

Eertree строится онлайн, то есть символ за символом, читая текст слева направо. При добавлении нового символа алгоритм просто проходит по суффиксным ссылкам последнего найденного палиндрома, проверяя, можно ли расширить его новым символом. Если получен новый уникальный палиндром — создается узел. Построение всей структуры занимает амортизированное время O(N).

Дерево палиндромов произвело фурор: оно позволило решать сложнейшие задачи строковой алгебры в несколько строчек элегантного кода. Сжатие данных, анализ РНК-цепочек в генетике и поиск паттернов в криптографии получили мощнейший и математически безупречный инструмент.