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