Алгоритм Манакера: поиск всех палиндромов за O(n)

Алгоритм Манакера (Manacher, 1975) находит все максимальные палиндромные подстроки строки длины $n$ за честное $O(n)$ - линейно, без логарифмов, без амортизаций «в среднем». Тот же результат позволяет за один проход решить классическую задачу о длиннейшей палиндромной подстроке (longest palindromic substring, LeetCode 5), на которую наивный алгоритм тратит $O(n^2)$, а решение через хеши - $O(n \log n)$ или $O(n)$ только в среднем. Манакер же даёт детерминированную верхнюю оценку при минимальных накладных расходах.

Зачем нужен отдельный алгоритм для палиндромов

Палиндромные подстроки устроены сложнее обычных. У них два типа - нечётные (центр в символе, как $\text{aba}$) и чётные (центр между символами, как $\text{abba}$). Перебор всех центров с расширением вправо-влево даёт $O(n^2)$ в худшем случае (на строке $\text{aaaaaa}$). Хеширование с бинарным поиском по радиусу - $O(n \log n)$, но всё равно работает «слепо», не используя тот факт, что палиндромы в строке наводятся друг на друга через симметрию.

Манакер заметил: если мы уже нашли длинный палиндром с центром $c$ и правым краем $r$, любая позиция $i \in [c, r]$ имеет «зеркало» $i' = 2c - i$ внутри уже исследованной области. Палиндром в зеркале даёт нижнюю оценку на палиндром в $i$ почти бесплатно. Дальше нужно только доуточнять явным расширением, а суммарное число таких расширений за весь прогон $\leq n$. Отсюда линейность.

Унификация чётных и нечётных палиндромов

Чтобы не писать два почти одинаковых цикла, перед запуском между всеми символами вставляют разделитель, который не встречается в алфавите - обычно #. Строку $s = \text{abba}$ превращают в

$s' = \#a\#b\#b\#a\#.$

Длина новой строки - $2n + 1$. Любой палиндром в $s$, чётный или нечётный, становится в $s'$ нечётным с центром на символе или на разделителе. Центр на букве - это исходный нечётный палиндром, центр на # - исходный чётный. Удобно: дальше работаем только с нечётными.

Граничные символы часто оборачивают в пару сторожей вида ^ и $, чтобы не проверять выход за границы явно - расширение остановится само, потому что ^ ≠ $.

Массив радиусов $p[i]$

Главная структура алгоритма - массив $p[i]$ длины $|s'| = 2n + 1$, где $p[i]$ - радиус максимального палиндрома с центром в $i$ (не считая сам центр). То есть подстрока $s'[i - p[i] \ldots i + p[i]]$ - палиндром, а $s'[i - p[i] - 1] \neq s'[i + p[i] + 1]$.

Если $p[i] = k$ в строке с разделителями, то в исходной строке палиндром имеет длину ровно $k$ (это не опечатка: за счёт расщепления символов разделителями радиус в $s'$ численно равен длине палиндрома в $s$).

Зная весь $p[\cdot]$, можно ответить на любой вопрос о палиндромах: длиннейший - $\max p[i]$ с восстановлением позиции; проверка «есть ли палиндром длины $L$» - за один линейный проход.

Зеркальный трюк: использование $c$ и $r$

Алгоритм поддерживает два указателя на лету:

• $c$ - центр того палиндрома среди найденных, у которого правая граница максимальна;
• $r = c + p[c]$ - сама правая граница (индекс самого правого символа внутри этого палиндрома).

Когда мы дошли до позиции $i$ и хотим вычислить $p[i]$, рассматриваем два случая.

Случай $i < r$. Внутри известного палиндрома с центром $c$ зеркальная позиция $i' = 2c - i$. Палиндром, центрированный в $i'$, уже вычислен - у него радиус $p[i']$. По симметрии относительно $c$ палиндром той же длины помещается и в $i$, если не выходит за правую границу $r$. Стартовое значение:

$p[i] = \min(r - i,\ p[2c - i]).$

Случай $i \geq r$. Полезной информации из зеркала нет, стартуем с $p[i] = 0$.

Дальше - явное расширение: пока $s'[i - p[i] - 1] = s'[i + p[i] + 1]$, увеличиваем $p[i]$ на 1. После расширения, если $i + p[i] > r$, обновляем $c \leftarrow i$, $r \leftarrow i + p[i]$ - теперь правая граница «съехала» дальше.

Псевдокод с инвариантом

s' = '#' + '#'.join(s) + '#'        # длина 2n + 1
p  = [0] * len(s')
c, r = 0, 0                          # инвариант: r = c + p[c], максимальный по r центр
for i in 1..len(s') - 1:
    if i < r:
        p[i] = min(r - i, p[2c - i])
    while i - p[i] - 1 >= 0
       and i + p[i] + 1 < len(s')
       and s'[i - p[i] - 1] == s'[i + p[i] + 1]:
        p[i] += 1
    if i + p[i] > r:
        c, r = i, i + p[i]

Инвариант перед итерацией: $r$ - самая правая позиция, которую покрывает уже найденный палиндром с центром в $c$. После итерации $i$ инвариант сохраняется, потому что мы обновляем $(c, r)$ только если $i + p[i] > r$ - то есть когда нашли палиндром, чей правый край ещё правее.

Почему это $O(n)$

Ключевой аргумент - амортизация числа явных расширений. Каждое успешное расширение на шаге $i$ увеличивает значение $r$ как минимум на единицу: если расширение прошло, это значит, что мы вышли за прежний правый край (иначе зеркальный трюк дал бы максимум $r - i$ и расширение не понадобилось бы). Переменная $r$ монотонно неубывающая и ограничена сверху $|s'| = 2n + 1$. Значит, суммарное число успешных расширений за весь прогон не превосходит $2n + 1$.

Неуспешное расширение (то, на котором цикл while остановился) - ровно одно на итерацию, итого $\leq 2n + 1$. Все остальные операции - константа на итерацию. Итого $O(n)$ операций, $O(n)$ дополнительной памяти под массив $p$.

Большинство «линейных» алгоритмов на строках (KMP, Z-функция) амортизируется через монотонно растущий указатель - Манакер из той же семьи доказательств.

Сравнение с другими подходами

Наивный $O(n^2)$. Перебор всех центров с расширением. На строках длины до $\sim 10^4$ работает мгновенно, но ломается на $\text{aaaa\ldots a}$: каждый центр даёт радиус $\sim n / 2$, итого $\Theta(n^2)$.

Хеши + бинарный поиск по радиусу. Для каждого центра двоичным поиском по длине палиндрома проверяем равенство префикса и его реверса через полиномиальный хеш, $O(n \log n)$ суммарно. Требует аккуратной работы с коллизиями (double hashing) и не даёт детерминированного результата.

Eertree (palindromic tree, Rubinstein-Shur, 2014). Хранит все различные палиндромные подстроки в специальной структуре: $O(n)$ узлов и построения, поддерживает онлайн-добавление символа. Богаче Манакера - можно считать частоты, искать вторые максимумы, - но реализация заметно сложнее. На одиночном прогоне Манакер выигрывает по константе.

Применения

• Longest palindromic substring (LeetCode 5). Каноническая задача собеседования. Манакер даёт $O(n)$ - лучшая известная асимптотика. После прогона $i^* = \arg\max p[i]$ и подстрока $s'[i^* - p[i^*]\ldots i^* + p[i^*]]$, очищенная от #, - ответ.
• Биоинформатика, палиндромы в ДНК. Молекулярные палиндромы - участки, где последовательность совпадает со своим обратным комплементом ($A \leftrightarrow T$, $C \leftrightarrow G$). После замены каждого нуклеотида на пару с комплементом задача сводится к обычным палиндромам, и Манакер находит сайты рестрикции за один линейный проход по геному.
• Сжатие. Палиндромные периоды используются в специализированных схемах сжатия повторяющихся текстов и в обнаружении дубликатов с реверсной симметрией.
• Подзадача в более сложных алгоритмах. Манакер вызывается как чёрный ящик в задачах «разрезать строку на минимальное число палиндромов» (palindrome partitioning DP), «посчитать палиндромные подстроки», «есть ли палиндром длины $\geq L$ с началом в позиции $i$».

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

• Пишут два цикла отдельно для чётных и нечётных палиндромов. Удваивает код и повышает вероятность бага. Унификация через # стоит трёх строк.
• Делают $p[i] = p[2c - i]$ без $\min(r - i, \cdot)$. Получается переоценка радиуса: палиндром в зеркале может выходить за левую границу палиндрома с центром $c$, и тогда симметрия не гарантирует совпадения за пределами $r$. Алгоритм начнёт «выдумывать» палиндромы.
• Не проверяют выход за границы строки в while. Без сторожевых символов или явной проверки получаем IndexError на палиндромах до края. Обёртка ^ и $ решает это элегантнее условия в цикле.
• Используют Манакер на двоичных строках, ожидая выигрыша против eertree. Для большого числа однотипных запросов eertree лучше - он кэширует все палиндромы. Манакер хорош для одиночного прогона.

FAQ

Чем алгоритм Манакера отличается от наивного поиска палиндромов? Наивный для каждого центра запускает расширение независимо, получая $O(n^2)$ на строках с длинными палиндромами. Манакер использует уже найденные палиндромы: если позиция $i$ лежит внутри известного палиндрома с центром $c$, её зеркало даёт стартовое значение радиуса бесплатно. Суммарное число явных расширений ограничено $2n$, отсюда $O(n)$ против $O(n^2)$.

Зачем вставлять # между символами? Чтобы унифицировать чётные и нечётные палиндромы. Без разделителей пришлось бы вести два массива $p_{\text{odd}}[i]$ и $p_{\text{even}}[i]$ и писать два цикла; с разделителями любой палиндром в $s'$ оказывается нечётным с центром либо на символе (исходный нечётный), либо на # (исходный чётный). Длина в $s'$ численно равна длине в $s$.

Можно ли построить Манакер онлайн, добавляя символы по одному? Базовый алгоритм - нет: при добавлении символа справа правый край $r$ может сдвинуться, и значения $p[i]$ для уже обработанных $i$ остаются актуальными, но новые палиндромы могут пересекать уже посчитанную область странным образом. Для онлайн-режима используют eertree - он специально спроектирован под потоковое добавление.

Коротко

Алгоритм Манакера находит все максимальные палиндромные подстроки строки длины $n$ за $O(n)$. Идея: вставка разделителей # унифицирует чётные и нечётные палиндромы, массив радиусов $p[i]$ заполняется с использованием зеркальной симметрии относительно текущего центра $c$ и правого края $r$ - стартовое значение $p[i] = \min(r - i, p[2c - i])$, дальше доуточнение явным расширением. Линейность доказывается через монотонность $r$: суммарное число успешных расширений не превосходит длины строки. На LeetCode 5, поиске сайтов рестрикции в ДНК и подзадачах palindrome partitioning Манакер - стандартный инструмент; альтернативный eertree богаче, но сложнее в реализации.