1:39:00 Определение. Тандемным повтором называется подстрока вида $LR$, где блоки $L$ и $R$ равны как строки и идут подряд. Повторов в строке может быть квадратично много (например, в строке из одной буквы), поэтому их считают не по отдельности, а в одной из компактных моделей — например, как множество троек «левая граница, длина половинки, сколько повторов с такой длиной есть, начинающихся в этой позиции». В такой модели троек оказывается $O(n\log n)$, и существует единый алгоритм, который находит их все за $O(n\log n)$.
Идея (разделяй и властвуй). Строку делят пополам: $S=S_0\ldots S_{m-1}\,S_m\ldots S_{n-1}$. Повторы, целиком лежащие слева или справа от середины, находятся рекурсией. Остаются повторы, пересекающие середину; из двух симметричных случаев (левая половинка повтора целиком слева от середины или целиком справа) достаточно считать один — второй считается тем же алгоритмом на развёрнутой строке.
Зафиксируем длину половинки повтора $L$ и обозначим $\mathrm{cnt}=m-L$ — позицию, с которой начинается правая половинка повтора (она же продолжение левой). Тогда $S_m=S_{\mathrm{cnt}}$, и чтобы восстановить $L$ по $\mathrm{cnt}$, достаточно считать $L=m-\mathrm{cnt}$ — значит, можно перебирать не длину, а саму позицию $\mathrm{cnt}$.
Для фиксированного $\mathrm{cnt}$ нужно проверить, на какую длину можно «растянуть» совпадение влево и вправо от середины так, чтобы начало левой половинки совпало с началом правой, а конец левой — с концом правой. Это ровно то, что считает Z-функция: одна Z-функция от развёрнутой левой части (считая от конца к $\mathrm{cnt}$) даёт максимальный общий префикс одной стороны, вторая Z-функция от правой части — максимальный общий префикс другой стороны. Сопоставив эти две границы, получаем отрезок допустимых длин повтора для текущего $\mathrm{cnt}$, то есть сразу целый диапазон троек, а не один повтор.
solve(S[l, r)):
если r − l ≤ 1: вернуть
m = (l + r) / 2
solve(S[l, m)); solve(S[m, r))
Z1 = Z-функция строки S[l, m) в обратном порядке (считаем от середины влево)
Z2 = Z-функция строки S[m, r) (считаем от середины вправо)
для cnt от l до r − 1:
A = largest prefix match влево, по Z1 в точке (m − cnt)
B = largest suffix match вправо, по Z2 в точке (cnt − m), если cnt ≥ m, иначе по симметричной формуле
если A + B ≥ |m − cnt|: есть отрезок допустимых длин повтора с данным cnt — добавить в ответ
учесть симметричный случай (правая половинка повтора целиком справа) на развёрнутой строкеРекурсия с работой $O(n)$ на каждом уровне даёт $O(n\log n)$ суммарно, а тройки «$\mathrm{cnt}$, границы допустимых длин» — компактная запись всех тандемных повторов, пересекающих середину, без явного перечисления каждого повтора.
1:41:40 Суффиксный массив строки с добавленным символом «минус бесконечность» в конце — это, по сути, сортировка всех циклических сдвигов строки: символ-страж обрубает каждый сдвиг снизу, и сравнение суффиксов становится сравнением сдвигов. Но если нужен не весь порядок, а только минимальный циклический сдвиг, есть более простой линейный алгоритм без построения суффиксного массива целиком.
Вырожденный случай. Если строка совпадает с каким-то своим нетривиальным циклическим сдвигом ($S_i=S_{(i+k)\bmod n}$ для всех $i$ и некоторого $k\neq 0$), то строка периодична с периодом $g=\gcd(k,n)$, который можно найти через Z-функцию, и минимальный сдвиг достаточно искать внутри одного периода. Дальше считаем, что все $n$ циклических сдвигов различны.
Алгоритм (сравнение сдвигов тройкой указателей). Поддерживаем два кандидата $i$ и $g$ на минимальный сдвиг и общую длину совпадения $k$ между ними (их наибольший общий префикс как бесконечно периодических строк). Пока символы на позициях $i+k$ и $g+k$ (по модулю $n$) совпадают, увеличиваем $k$. Как только находим расхождение, скажем, сдвиг с $g$ оказался строго меньше: тогда все сдвиги, начинающиеся в позициях от $i$ до $i+k$ включительно, гарантированно не минимальны (сдвиг, начинающийся на один символ правее текущего лучшего, всегда не хуже), поэтому сразу переносим $i$ на $i+k+1$ и обнуляем $k$. Итерации продолжаются, пока один из указателей не выйдет за пределы строки — второй указывает на минимальный сдвиг.
int minCyclicShift(const string& s) {
int n = s.size();
int i = 0, g = 1, k = 0;
while (i < n && g < n) {
char a = s[(i + k) % n], b = s[(g + k) % n];
if (a == b) { k++; continue; }
if (a > b) i += k + 1; else g += k + 1;
if (i == g) g++;
k = 0;
}
return min(i, g);
}Корректность видна сразу из рассуждения выше; быстрота — из того, что за каждый шаг цикла сумма $i+g+k$ растёт как минимум на единицу, а $k$ при переносе указателя теряется — суммарно указатели проходят строку не более нескольких раз, то есть алгоритм линейный.
1:56:00 Суффиксный массив. Суффикс $\mathrm{suf}_i$ строки $S_0\ldots S_{n-1}$ — это $S_i S_{i+1}\ldots S_{n-1}$. Все $n$ суффиксов различны как строки (хотя бы по длине), поэтому их можно строго отсортировать лексикографически. Суффиксный массив $p_0,\ldots,p_{n-1}$ — это перестановка индексов $0,\ldots,n-1$ такая, что $\mathrm{suf}_{p_0}<\mathrm{suf}_{p_1}<\ldots<\mathrm{suf}_{p_{n-1}}$. Храним не сами суффиксы, а только их начальные позиции — это даёт линейную память вместо квадратичной.
LCP-массив. $\mathrm{lcp}_i$ ($i=0,\ldots,n-2$) — длина наибольшего общего префикса соседних в сортировке суффиксов, $\mathrm{suf}_{p_i}$ и $\mathrm{suf}_{p_{i+1}}$. Эти два массива вместе заменяют само дерево или автомат суффиксов почти во всех задачах.
2:04:28 Наивно LCP между двумя произвольными суффиксами считается попарным сравнением за $O(n)$, и построение всего массива так заняло бы $O(n^2)$. Алгоритм Касаи (в литературе встречается с несколькими соавторами) строит LCP-массив за линию, если суффиксный массив уже построен — хотя сам по себе этот алгоритм довольно нишевый: суффиксный массив обычно и так строится не быстрее $O(n\log n)$, так что линейность LCP-шага редко становится узким местом.
Идея — пройти по суффиксам не в порядке их начала в строке, а в порядке убывания длины (от $S_0\ldots S_{n-1}$ до одиночного символа), поддерживая текущее значение LCP $k$ с соседом в суффиксном массиве. Пусть известно, что $\mathrm{suf}_g$ и его соседний (следующий по сортировке) суффикс $\mathrm{suf}_{p+1}$ имеют $\mathrm{lcp}=k$ (где $g=p_i$ для позиции $i$ в суффиксном массиве). Переходя к более короткому суффиксу $\mathrm{suf}_{g+1}$, замечаем: сосед $\mathrm{suf}_{p+1}$ отбросил свой первый символ и превратился в $\mathrm{suf}_{p+2}$, у которого с $\mathrm{suf}_{g+1}$ общий префикс не меньше $k-1$ — то есть при переходе к соседней позиции $g+1$ её LCP с ближайшим соседом по суффиксному массиву не может упасть ниже $k-1$. Поэтому $k$ пересчитывается без обнуления: берём $\max(k-1,0)$ как стартовое значение и дотягиваем его посимвольным сравнением (`while`), а не считаем с нуля.
vector<int> kasai(const string& s, const vector<int>& p) {
int n = s.size();
vector<int> rank(n), lcp(n - 1);
for (int i = 0; i < n; i++) rank[p[i]] = i; // обратная перестановка: позиция суффикса g в суфмассиве
int k = 0;
for (int g = 0; g < n; g++) {
if (rank[g] == n - 1) { k = 0; continue; } // у последнего в сортировке соседа справа нет
int j = p[rank[g] + 1]; // соседний суффикс в суфмассиве
while (g + k < n && j + k < n && s[g + k] == s[j + k]) k++;
lcp[rank[g]] = k;
k = max(k - 1, 0);
}
return lcp;
}Суммарно счётчик $k$ увеличивается не более $n$ раз (цикл `for`) и уменьшается не более чем на $1$ за внешнюю итерацию, поэтому суммарная работа всех внутренних `while` линейна.
2:22:30 Задача. Посчитать число различных подстрок строки длины $n$.
Любая подстрока — префикс какого-то суффикса, а суффиксов $n$, так что верхняя оценка — $\sum_{i=1}^n i=\tfrac{n(n+1)}{2}$ (сумма длин всех суффиксов), но часть префиксов повторяется между соседними в сортировке суффиксами. Если идти по суффиксному массиву слева направо, префиксы текущего суффикса длиной до $\mathrm{lcp}_{i-1}$ совпадают с префиксами предыдущего (уже посчитанными), а более длинные — встречаются впервые, потому что они отличаются и от непосредственного соседа, и тем более от более далёких суффиксов (у которых LCP с текущим не больше, по свойству минимума на отрезке). Значит, новых подстрок от суффикса $\mathrm{suf}_{p_i}$ ровно $(n-p_i)-\mathrm{lcp}_{i-1}$ (считая $\mathrm{lcp}_{-1}=0$).
Та же задача легко решается суффиксным деревом или суффиксным автоматом — это общее свойство суффиксных структур: почти любая задача, решаемая одной из них, решается и любой другой, вопрос только в том, какая даёт более удобную асимптотику или более простой код для конкретной задачи. У суффиксного массива время построения $O(n\log n)$, но версия на автомате или дереве бора может платить лишним множителем на размер алфавита (хранить переходы картой, а не массивом) там, где суффиксный массив этого избегает.
2:30:00 Задача. Дан текст $S$ (суффиксная структура строится по нему заранее), запросами приходят образцы $Q$; для каждого нужно проверить вхождение, посчитать число вхождений или найти первое вхождение.
Наивный бинарный поиск положения $Q$ среди суффиксов работает за $O(|Q|\log n)$: на каждом шаге сравниваем $Q$ с очередным суффиксом посимвольно. Это можно ускорить до $O(|Q|+\log n)$, если во время бинарного поиска переносить между итерациями уже известные значения LCP с границами текущего отрезка $[l,r]$: для середины $m$ нижняя граница $\mathrm{lcp}(Q,\mathrm{suf}_{p_m})\ge\min(\mathrm{lcp}(Q,\mathrm{suf}_{p_l}),\mathrm{lcp}(\mathrm{suf}_{p_l},\mathrm{suf}_{p_m}))$ (аналогично для правой границы) известна заранее через минимум на отрезке LCP-массива, и дотягивать совпадение посимвольно нужно только с того места, где гарантии заканчиваются. Суммарно по всем шагам бинарного поиска счётчик LCP с текущим образцом двигается вперёд не более $O(|Q|)$ раз, что и даёт итоговую оценку $O(|Q|+\log n)$.
Найдя левую и правую границы отрезка суффиксного массива с $\mathrm{lcp}(Q,\cdot)=|Q|$ двумя такими бинарными поисками, получаем число вхождений как длину отрезка, а первое вхождение в тексте — как минимум индексов $p_i$ на этом отрезке.
2:40:30 Задача. Для строк $S$ и $T$ найти длину наибольшей общей подстроки.
Склеиваем $S\,\$_1\,T\,\$_2$ двумя разными символами-стражами (строго меньше любого символа алфавита и разными, чтобы суффиксы с $\$_1$ и $\$_2$ не сливались) и строим суффиксную структуру на склейке. В отсортированном порядке суффиксов любые два соседних суффикса, один из которых начинается в $S$, а другой — в $T$, дают общую подстроку длины $\mathrm{lcp}$ между ними; максимум такого LCP среди всех пар разнородных соседей и есть ответ. Доказательство: если у суффикса из $S$ и суффикса из $T$ общий префикс длины $k$, то между ними в сортировке лежат только суффиксы с префиксом не короче $k$ (иначе нарушился бы порядок), поэтому максимум обязательно достигается на каких-то соседних позициях.
2:47:48 Строим суффиксный массив как частный случай сортировки циклических сдвигов (строка с добавленным символом-стражем в конце не даёт циклическим сдвигам «обернуться» через конец, поэтому сортировка сдвигов совпадает с сортировкой суффиксов). Алгоритм — вариант поразрядной сортировки (radix sort) с удвоением длины блока на каждом шаге.
Шаг 0. Сортируем одиночные символы подсчётом (за $O(n+|\Sigma|)$) и присваиваем каждой позиции класс эквивалентности $c_0[i]$ — номер группы одинаковых символов в этом порядке (минимальный символ строки получает класс $0$ и так далее).
Шаг $k\to k+1$. Есть порядок $p_k$ и классы эквивалентности $c_k$ «прыжков» длины $2^k$ (прыжок из позиции $i$ — это подстрока $S_i\ldots S_{i+2^k-1}$, индексы по модулю $n$, потому что работаем с циклическими сдвигами). Прыжок длины $2^{k+1}$ из позиции $i$ — это просто пара прыжков длины $2^k$: из $i$ и из $i+2^k$. Чтобы сравнить такие пары лексикографически, достаточно сравнить пары $(c_k[i], c_k[i+2^k])$ — и это задача ровно для поразрядной сортировки за линию: правая компонента пары уже отсортирована порядком $p_k$ (устойчивая сортировка по левой компоненте его не портит), а левая компонента — это целые числа от $0$ до $n-1$, которые сортируются подсчётом.
vector<int> buildSuffixArray(string s) {
s += '\x01'; // символ-страж, меньше любого символа алфавита
int n = s.size();
vector<int> p(n), c(n), cnt(max(256, n));
for (char ch : s) cnt[ch]++;
for (int i = 1; i < 256; i++) cnt[i] += cnt[i - 1];
for (int i = 0; i < n; i++) p[--cnt[s[i]]] = i;
c[p[0]] = 0;
for (int i = 1; i < n; i++)
c[p[i]] = c[p[i - 1]] + (s[p[i]] != s[p[i - 1]]);
for (int k = 0; (1 << k) < n; k++) {
int half = 1 << k;
vector<int> pNew(n), cNew(n);
for (int i = 0; i < n; i++) pNew[i] = (p[i] - half % n + n) % n; // перебор по убыванию правых половинок
fill(cnt.begin(), cnt.begin() + n, 0);
for (int i = 0; i < n; i++) cnt[c[pNew[i]]]++;
for (int i = 1; i < n; i++) cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; i--) p[--cnt[c[pNew[i]]]] = pNew[i];
cNew[p[0]] = 0;
for (int i = 1; i < n; i++) {
pair<int,int> prev = {c[p[i - 1]], c[(p[i - 1] + half) % n]};
pair<int,int> cur = {c[p[i]], c[(p[i] + half) % n]};
cNew[p[i]] = cNew[p[i - 1]] + (cur != prev);
}
c = cNew;
if (c[p[n - 1]] == n - 1) break; // все классы различны — массив готов
}
p.erase(p.begin()); // убираем позицию символа-стража
return p;
}Каждый из $O(\log n)$ шагов делает $O(n)$ работы (две сортировки подсчётом плюс один линейный проход), итого $O(n\log n)$ по времени и $O(n)$ по памяти. Остановиться можно раньше полного числа шагов, если классы эквивалентности уже все различны — дальше сравнивать нечего.