Палиндромы

Палиндромы

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

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

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

Пусть есть строка \(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;
}

Значение в массиве r в дальнейшем будем называть радиусом палиндрома.

Тот же пример \(s = aa\dots a\) показывает, что данная реализация работает за \(O(n^2)\). Для оптимизации, применим идею, знакомую из алгоритма z-функции: при инициализации \(r\) будем пользоваться уже посчитанными \(r\).

Будем поддерживать \((l, r)\) — интервал, соответствующий самому правому из найденных подпалиндромов. Тогда мы можем сказать, что часть наибольшего палиндрома с центром в \(s_i\), которая лежит в \(s_{l:r}\) имеет радиус \(\min(r-i, len_{l+r-i})\).

\((r-i)\) означает длину при которой произошёл бы выход за \(S_{(l, r)}\), а \(len_{l+r-i}\) – значение \(len\) в позиции, зеркальной относительно центра \(S_{(l, r)}\).

vector<int> pal_array(string s)
{
    int n = s.size();
    s = "@" + s + "$";
    vector<int> len(n + 1);
    int l = 1, r = 1;
    for(int i = 1; i <= n; i++)
    {
        len[i] = min(r - i, len[l + (r - i)]);
        while(s[i - len[i]] == s[i + len[i]])
            len[i]++;
        if(i + len[i] > r)
        {
            l = i - len[i];
            r = i + len[i];
        }
    }
    len.erase(begin(len));
    return len;
}

Так же, как и z-функция, алгоритм работает за линейное время.

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

Чтобы учесть чётные палиндромы, сделаем замену: \(S = s_1 s_2 \dots s_n \to S^* = s_1 \# s_2 \# \dots \# s_n\). Теперь нечётные палиндромы с центром в \(s_i\) соответствуют нечётным палиндромам исходной строки, а нечётные палиндромы с центром в \(\#\) – чётным.

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

Данная структура, предложенная Михаилом Рубинчиком, представляет собой другой формат хранения информации обо всех подпалиндромах строки, более мощный по своей сути. чем \(n\) палиндромов. Пусть мы наращиваем строку по одному символу и в

Сперва докажем, что у любой строки есть не больше, данный момент имеем наибольший суффикс-палиндром \(S_{l,r}\). Пусть у него есть суффикс-палиндром \(S_{l',r}\). Тогда он уже имеет вхождение в позиции \(S_{l,l+r-l'}\). Таким образом, с каждым новым символом у строки появляется не более одного нового палиндрома и если таковой есть, то это всегда наибольший суффикс-палиндром.

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

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

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

Наконец, приведём реализацию указанного алгоритма:

const int maxn = 1e5 + 42;
map<char, int> to[maxn];
int len[maxn], link[maxn], s[maxn];
int sz, n, last;

void init() // Начальные значения, чтобы не возиться с границами
{
    link[0] = 1;
    len[1] = -1;
    s[n++] = -1;
    sz = 2;
}

int get_link(int v) // Суффикс v, который дополняется до палиндрома
{
    while(s[n - len[v] - 2] != s[n - 1])
        v = link[v];
    return v;
}

void add_letter(char 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];
}

Как и в случае с Ахо-Корасик, существуют неамортизированные \(O(n \Sigma)\) и \(O(n \log \Sigma)\) версии.