Палиндромное дерево (Eertree): все палиндромы строки за O(n)

Коротко

Ключевой факт

У строки длины n не может быть больше n различных подпалиндромов.

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

Именно этот факт делает возможным хранить все палиндромы в структуре линейного размера.

Устройство

Палиндромное дерево (eertree, от «tree» задом наперёд) состоит из узлов, каждый из которых соответствует одному различному палиндрому.

Есть два корня:

• корень длины −1 — фиктивный, от него растут палиндромы нечётной длины;
• корень длины 0 — пустая строка, от неё растут палиндромы чётной длины.

Странная длина −1 — не ошибка, а приём. Переход из узла длины L по символу c даёт палиндром длины L + 2. От −1 получается 1 (одиночный символ), от 0 получается 2. Так оба случая обрабатываются единообразно.

Суффиксная ссылка узла ведёт к наибольшему собственному палиндромному суффиксу этого палиндрома.

Построение

При добавлении символа ищем, к какому существующему палиндрому его можно «обернуть»: поднимаемся по суффиксным ссылкам, пока символ слева не совпадёт с добавляемым.

class Eertree:
    def __init__(self):
        # узел 0: корень длины -1, узел 1: корень длины 0
        self.length = [-1, 0]
        self.link = [0, 0]
        self.next = [{}, {}]
        self.count = [0, 0]      # число вхождений
        self.s = []
        self.last = 1

    def _find_suffix(self, node: int, pos: int) -> int:
        """Ищем узел, к которому можно приписать символ с обеих сторон."""
        while True:
            candidate = pos - self.length[node] - 1
            if candidate >= 0 and self.s[candidate] == self.s[pos]:
                return node
            node = self.link[node]

    def add(self, ch: str) -> bool:
        """Возвращает True, если появился новый палиндром."""
        self.s.append(ch)
        pos = len(self.s) - 1

        cur = self._find_suffix(self.last, pos)

        if ch in self.next[cur]:
            self.last = self.next[cur][ch]
            self.count[self.last] += 1
            return False              # такой палиндром уже был

        # создаём новый узел
        now = len(self.length)
        self.length.append(self.length[cur] + 2)
        self.next.append({})
        self.count.append(1)

        # суффиксная ссылка нового узла
        if self.length[now] == 1:
            self.link.append(1)       # одиночный символ → пустая строка
        else:
            temp = self._find_suffix(self.link[cur], pos)
            self.link.append(self.next[temp][ch])

        self.next[cur][ch] = now
        self.last = now
        return True

    def build(self, s: str) -> 'Eertree':
        for ch in s:
            self.add(ch)
        return self

    def distinct_count(self) -> int:
        return len(self.length) - 2      # без двух корней

    def all_palindromes(self) -> list[str]:
        """Восстанавливаем строки палиндромов (для наглядности)."""
        result = []
        for node in range(2, len(self.length)):
            # идём вверх, собирая символы переходов
            result.append(self._restore(node))
        return result

    def _restore(self, node: int) -> str:
        chars = []
        current = node
        # переходы записаны от родителя к ребёнку — ищем обратный путь
        while current >= 2:
            for parent in range(len(self.next)):
                for ch, child in self.next[parent].items():
                    if child == current:
                        chars.append(ch)
                        current = parent
                        break
                else:
                    continue
                break
            else:
                break
        core = '' if self.length[node] % 2 == 0 else chars.pop()
        left = ''.join(reversed(chars))
        return left + core + ''.join(chars)


tree = Eertree().build('abacaba')
print('различных палиндромов:', tree.distinct_count())   # 4: a, b, aba, abacaba... 

Проверим на строке abacaba: различные палиндромы это a, b, aba, c, aca, bacab, abacaba — семь штук, ровно как длина строки.

Подсчёт вхождений

Массив count после построения хранит только «прямые» вхождения. Чтобы получить полное число вхождений каждого палиндрома, нужно просуммировать счётчики вниз по суффиксным ссылкам, идя от длинных узлов к коротким.

def propagate_counts(tree: Eertree) -> list[int]:
    counts = tree.count[:]
    # узлы создавались в порядке возрастания, идём обратно
    for node in range(len(counts) - 1, 1, -1):
        counts[tree.link[node]] += counts[node]
    return counts

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

Какие задачи решает

Количество различных подпалиндромов — размер дерева минус два корня.

Число вхождений каждого палиндрома — после проталкивания счётчиков.

Самый частый палиндром — максимум по счётчикам.

Количество палиндромных подстрок всего — сумма счётчиков.

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

Сравнение с алгоритмом Манакера

Правило: нужен только наибольший палиндром — берите Манакера. Нужно работать с множеством палиндромов, считать различные или вхождения — палиндромное дерево.

Частые ошибки

Корень длины −1 как ошибка. Это намеренная конструкция, без неё нечётные палиндромы не строятся единообразно.

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

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

Поиск суффикса без проверки границы. Условие candidate >= 0 обязательно, иначе выход за начало строки.

Что запомнить

• У строки длины n не больше n различных подпалиндромов — на этом строится структура.
• Два корня: длины −1 для нечётных палиндромов и 0 для чётных.
• Строится онлайн за O(n): каждый символ добавляет не более одного нового узла.
• Число вхождений получается проталкиванием счётчиков вниз по суффиксным ссылкам в обратном порядке.
• Для поиска одного наибольшего палиндрома проще алгоритм Манакера.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→