manacher.md

title	Алгоритм Манакера
authors	Сергей Слотин
created	2019
weight	3

Пусть есть строка $s$ и мы хотим найти в ней все подпалиндромы.

Мы сразу сталкиваемся с очевидной трудностью: их в строке может быть $O(n^2)$, что можно видеть на примере строки $s = aa \ldots a$. Поэтому будем использовать следующий формат: для каждой позиции $s_i$ найдём наибольший палиндром, центр которого совпадает с $s_i$ (чётные и нечётные палиндромы будем рассматривать отдельно). Половину его длины, округлённую вниз, будем называть радиусом.

Наивное решение — перебрать $s_i$, а для него вторым циклом находить наибольшую искомую длину:

vector<int> pal_array(string s) {
    int n = s.size();

    // окружим строку спецсимволами, чтобы не рассматривать выход за границы
    s = "#" + s + "$";

    // в этом массиве будем хранить расстояние от центра до границы палиндрома
    vector<int> r(n, 0);

    for(int i = 1; i <= n; i++)
        while (s[i - r[i - 1]] == s[i + r[i - 1]])
            r[i-1]++;

    return r;
}

Тот же пример $s = aa\dots a$ показывает, что данная реализация работает за $O(n^2)$.

Для оптимизации применим идею, знакомую из алгоритма z-функции: при инициализации $t_i$ будем пользоваться уже посчитанными $t$. А именно, будем поддерживать $(l, r)$ — интервал, соответствующий самому правому из найденных подпалиндромов. Тогда мы можем сказать, что часть наибольшего палиндрома с центром в $s_i$, которая лежит внутри $s_{l:r}$, имеет радиус хотя бы $\min(r-i, ; t_{l+r-i})$. Первая величина равна длине, дальше которой произошел бы выход за пределы $s_{l:r}$, а вторая — значению радиуса в позиции, зеркальной относительно центра палиндрома $s_{l:r}$.

vector<int> manacher_odd(string s) {
    int n = (int) s.size();
    vector<int> d(n, 1);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r)
            d[i] = min(r - i + 1, d[l + r - i]);
        while (i - d[i] >= 0 && i + d[i] < n && s[i - d[i]] == s[i + d[i]])
            d[i]++;
        if (i + d[i] - 1 > r)
            l = i - d[i] + 1, r = i + d[i] - 1;
    }
    return d;
}

Так же, как и z-функция, алгоритм работает за линейное время: цикл while запускается только когда $t_i = r - i$ (иначе палиндром уже во что-то упёрся), и каждая его итерация сдвигает увеличивает $r$ на единицу. Так как $r \leq n$, получаем, что суммарно эти циклы сделают $O(n)$ итераций.

Для случая чётных палиндромов меняется только индексация:

vector<int> manacher_even(string s) {
    int n = (int) s.size();
    vector<int> d(n, 0);
    int l = -1, r = -1;
    for (int i = 0; i < n - 1; i++) {
        if (i < r)
            d[i] = min(r - i, d[l + r - i - 1]);
        while (i - d[i] >= 0 && i + d[i] + 1 < n && s[i - d[i]] == s[i + d[i] + 1])
            d[i]++;
        if (i + d[i] > r)
            l = i - d[i] + 1, r = i + d[i];
    }
    return d;
}

Также можно было не писать отдельно две реализации, а воспользоваться следующим трюком — сделать замену:

$$ S = s_1 s_2 \dots s_n \to S^* = s_1 # s_2 # \dots # s_n $$

Теперь нечётные палиндромы с центром в $s_i$ соответствуют нечётным палиндромам исходной строки, а нечётные палиндромы с центром в # — чётным.