palindromes.md

Палиндромы

Палиндром — это фраза, которая читается одинаково слева направо и справа налево. Например:

• «was it a car or a cat I saw?»

• «а роза упала на лапу Азора»

• «abacaba» (палиндром нечётной длины)

• «abba» (палиндром чётной длины)

Для простоты, мы будем рассматривать только последовательности из строчных латинских букв.

Палиндромы — не самые часто встречающиеся в реальной жизни объекты, однако задачи на палиндромы любят давать на соревнованиях по спортивному программированию. В этой статье мы опишем эффективные способы их представления.

Алгоритм Манакера

Пусть есть строка $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> t(n, 0);

    for(int i = 1; i <= n; i++)
        while (s[i - t[i - 1]] == s[i + t[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$ соответствуют нечётным палиндромам исходной строки, а нечётные палиндромы с центром в $#$ — чётным.

Дерево палиндромов

Дерево палиндромов (англ. palindromic tree, EERTREE) — структура данных, использующая другой, более мощный формат хранения информации обо всех подпалиндромах, чем размеры $n$ палиндромов. Она была предложена Михаилом Рубинчиком на летних петрозаводских сборах в 2014-м году.

Лемма. В строке есть не более $n$ различных подпалиндромов.

Доказательство. Пусть мы дописываем к строке по одному символу и в данный момент, записав $r$ символов, имеем наибольший суффикс-палиндром $s_{l:r}$. Пусть у него, в свою очередь, есть суффикс-палиндром $s_{l':r} = t$. Тогда он также имеет более раннее вхождение в строку как $s_{l:l+r-l'} = t$. Таким образом, с каждым новым символом у строки появляется не более одного нового палиндрома, и если таковой есть, то это всегда наибольший суффикс-палиндром.

Этот факт позволяет сопоставить всем палиндромам строки сопоставить следующую структуру: возьмём от каждого палиндрома его правую половину (например, $caba$ для $abacaba$ или $ba$ для $abba$; будем рассматривать пока что только чётные палиндромы) и добавим все эти половины в префиксное дерево — получившуюся структуру и будем называть деревом палиндромов.

Наивный алгоритм построения будет в худшем случае работать за $O(n^2)$, но это можно делать и более эффективно.

Построение за линейное время

Будем поддерживать наибольший суффикс-палиндром. Когда мы будем дописывать очередной символ $c$, нужно найти наибольший суффикс этого палиндрома, который может быть дополнен символом $c$ — это и будет новый наидлиннейший суффикс-палиндром.

Для этого поступим аналогично алгоритму Ахо-Корасик: будем поддерживать для каждого палиндрома суффиксную ссылку $l(v)$, ведущую из $v$ в её наибольший суффикс-палиндром. При добавлении очередного символа, будем подниматься по суффиксным ссылкам, пока не найдём вершину, из которой можно совершить нужный переход.

Если в подходящей вершине этого перехода не существовало, то нужно создать новую вершину, и для неё тоже понадобится своя суффиксная ссылка. Чтобы найти её, будем продолжать подниматься по суффиксным ссылкам предыдущего суффикс-палиндрома, пока не найдём второе такое место, которое мы можем дополнить символом $c$.

const int maxn = 1e5, k = 26;

int s[maxn], len[maxn], link[maxn], to[maxn][k];

int n, last, sz;

void init() {
    s[n++] = -1;
    link[0] = 1;
    len[1] = -1;
    sz = 2;
}

int get_link(int v) {
    while (s[n-len[v]-2] != s[n-1])
        v = link[v];
    return v;
}

void add_char(int c) {
    s[n++] = c;
    last = get_link(last);
    if (!to[last][c]) {
        len[sz] = len[last] + 2;
        link[sz] = to[get_link(link[last])][c];
        to[last][c] = sz++;
    }
    last = to[last][c];
}

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

Асимптотика

Покажем линейность алгоритма. Рассмотрим длину наибольшего суффикс-палиндрома строки. Каждый новый символ увеличивает её не более, чем на 2. При этом каждый переход по суффиксной ссылке уменьшает её, поэтому нахождение первого суффикс-палиндрома амортизировано работает за линейное время.

Аналогичными рассуждениями о длине второго суффикс-палиндрома (его длина увеличивается тоже не более, чем на 2) получаем, что пересчёт суффиксных ссылок при создании новых вершин тоже суммарно работает за линейное время.