Палиндромы

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

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

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

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

Пусть есть строка \(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) получаем, что пересчёт суффиксных ссылок при создании новых вершин тоже суммарно работает за линейное время.