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

Палиндром задаётся центром и радиусом. Центров у строки длины $n$ ровно $2n - 1$: $n$ символов и $n - 1$ промежутков между ними.

Алгоритм Манакера для каждого центра находит наибольший палиндром с этим центром. Всё остальное про палиндромы выводится отсюда.

Держат два массива:

• $d_1[i]$ - количество нечётных палиндромов с центром в $i$, оно же радиус вместе с центром. Палиндром занимает $[i - d_1[i] + 1,\; i + d_1[i] - 1]$;
• $d_2[i]$ - количество чётных палиндромов с центром между $i-1$ и $i$. Палиндром занимает $[i - d_2[i],\; i + d_2[i] - 1]$.

Для abaaba: $d_1 = [1, 2, 1, 1, 2, 1]$, $d_2 = [0, 0, 0, 3, 0, 0]$. Единственный чётный палиндром длиной больше нуля - вся строка, и её центр лежит между позициями 2 и 3.

Наивно и почему это плохо

Для каждого центра расходиться в обе стороны - $O(n^2)$. На строке из одинаковых букв это ровно $n^2/4$ сравнений: при $n = 10^5$ уже $2{,}5 \cdot 10^9$.

Ускорение то же, что в z-функции: переиспользовать посчитанное.

Самое правое палиндромное окно

Держим границы $[l, r]$ - того из уже найденных палиндромов, который кончается правее всех.

Если новый центр $i$ попал внутрь, то зеркальная относительно центра окна позиция $l + r - i$ уже посчитана, и её ответ можно списать. Но только до правой границы: дальше окна мы про строку ничего не знаем.

$$d_1[i] \ge \min(d_1[l + r - i],\; r - i + 1)$$

Дальше - досравнивание вручную и, если палиндром вылез правее $r$, обновление окна.

vector<int> d1(n), d2(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
    int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
    while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) k++;
    d1[i] = k--;
    if (i + k > r) { l = i - k; r = i + k; }
}
for (int i = 0, l = 0, r = -1; i < n; i++) {
    int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
    while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k]) k++;
    d2[i] = k--;
    if (i + k > r) { l = i - k - 1; r = i + k; }
}

Два цикла отличаются тремя мелочами: начальным значением $k$, смещением индекса при списывании ($+1$) и левой границей при обновлении окна ($-1$). Эти три места - главный источник ошибок; их стоит выписать один раз и больше не выводить заново.

Проверено: на 4000 случайных строках длины до 14 над алфавитами из 1-3 букв счёт палиндромных подстрок и наибольший палиндром совпали с полным перебором всех подстрок.

Почему линия

Тот же амортизационный аргумент, что и везде в разделе: каждое успешное сравнение внутри while двигает правую границу $r$ вправо хотя бы на единицу, а $r$ не убывает и не превосходит $n$. Неуспешное сравнение в каждой итерации ровно одно.

Измерено (оба прохода вместе):

строка	длина	сравнений	доля от $n$
случайная, алфавит 26	1 000 000	2 080 088	2,08
случайная, алфавит 2	1 000 000	3 464 024	3,46
aaaa…	1 000 000	1 999 997	2,00
abab…	1 000 000	1 999 997	2,00
палиндром из 10^6 букв	1 000 000	2 560 568	2,56

Доля около двух - это и есть «одно неуспешное сравнение на центр, а центров $2n$». Успешных сравнений заметно меньше: они и ограничены движением $r$.

Что из этого следует

Количество палиндромных подстрок - просто сумма: $\sum d_1[i] + \sum d_2[i]$. Каждый палиндром считается один раз, по своему центру.

Наибольшая палиндромная подстрока - максимум по $2 d_1[i] - 1$ и $2 d_2[i]$.

Является ли $s[l..r]$ палиндромом - да, если радиус в центре этого отрезка достаёт до его краёв. Для нечётной длины центр $\frac{l+r}{2}$, для чётной - $\frac{l+r+1}{2}$.

Наибольший палиндромный префикс - максимум по палиндромам, у которых левая граница равна нулю; аналогично для суффикса. Впрочем, для одной такой задачи Манакер избыточен: хватает склейки с перевёрнутой строкой.

Манакер или хеши

Палиндромы ищут и хешами: для центра бинарным поиском находят наибольший радиус, сравнивая прямой хеш с обратным. Это $O(n \log n)$ и вероятностно.

	Манакер	хеши с бинпоиском
время	$O(n)$	$O(n \log n)$
ответ	точный	вероятностный
длина кода	12 строк, легко ошибиться	20 строк, ошибиться труднее
обобщается на «почти палиндром»	плохо	хорошо

Правило: если задача чисто про палиндромы - Манакер. Если палиндромы это лишь часть задачи, где уже нужны хеши, - не заводите второй инструмент.