Бордер строки $S$ — это её префикс, равный её суффиксу (при наложении символы должны совпадать). Например, у строки аааааа много бордеров.
Вся строка тоже является своим префиксом-суффиксом, поэтому вводят понятие собственного бордера — бордера, не совпадающего со всей строкой.
Наивно. Перебираем все префиксы, для каждого перебираем все длины и проверяем равенство префикса и суффикса — это $O(n^3)$.
Улучшение. Два наблюдения:
Поэтому для нового префикса достаточно перебирать длины от $\pi[i-1]+1$ вниз до нуля. Получаем $O(n^2)$: суммарно внутренний цикл делает $O(n)$ подъёмов (по +1 на итерацию) и $O(n)$ спусков (каждый спуск «окупается» предшествующим подъёмом).
При переборе кандидатов-бордеров мы заново проверяем, что «почти вся» строка совпадает с префиксом. Но для кандидата, у которого всё, кроме последнего символа, заведомо совпадает, проверять нужно только один символ.
Ключевой факт. Все длины-кандидаты (префиксы, равные суффиксу, для которых всё, кроме последнего символа, уже проверено) — это в точности цепочка бордеров: $\pi[i-1],\ \pi[\pi[i-1]-1],\ \pi[\pi[\pi[i-1]-1]-1], \dots$ до нуля. Поэтому, когда кандидат не подошёл (последние символы не равны), переходим не к следующей длине, а к бордеру этого бордера.
Алгоритм: $j$ — длина текущего кандидата (изначально $\pi[i-1]$). Пока $j > 0$ и $S[j] \ne S[i]$ — делаем $j = \pi[j-1]$. Затем, если $S[j] = S[i]$, увеличиваем $j$. В конце $\pi[i] = j$.
vector<int> prefix_function(const string& s) {
int n = s.size();
vector<int> pi(n, 0);
for (int i = 1; i < n; ++i) {
int j = pi[i - 1];
while (j > 0 && s[j] != s[i])
j = pi[j - 1]; // переходим к бордеру бордера
if (s[j] == s[i]) ++j;
pi[i] = j;
}
return pi;
}Задача. Найти все вхождения шаблона $S$ в текст $T$.
Идея. Склеиваем строку $S\ \#\ T$, где $\#$ — разделитель, не встречающийся ни в $S$, ни в $T$. Считаем префикс-функцию этой строки. В позиции, где $\pi$ равно $|S|$, заканчивается вхождение шаблона.
Зачем разделитель? Без него префикс-функция могла бы «перетечь» через границу шаблона и текста и выдать ложное вхождение (например, шаблон аа в тексте ааа дал бы бордер, пересекающий границу). Разделитель гарантирует, что $\pi$ никогда не превысит $|S|$.
Сложность — $O(|S| + |T|)$.
Z-функция $z[i]$ строки — длина наибольшего префикса строки, совпадающего со строкой, начинающейся с позиции $i$ (то есть наибольший общий префикс всей строки и суффикса $S[i..]$).
Поддерживаем самое правое из «изведанных» совпадений — отрезок $[l, r)$, где строка $S[l..r)$ совпадает с префиксом $S[0..r-l)$.
vector<int> z_function(const string& s) {
int n = s.size();
vector<int> z(n);
int l = 0, r = 0;
for (int i = 1; i < n; ++i) {
if (i < r)
z[i] = min(r - i, z[i - l]); // заведомо совпадающий кусок
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
++z[i];
if (i + z[i] > r) { // расширили правую границу
l = i;
r = i + z[i];
}
}
return z;
}Идея. Если позиция $i$ лежит внутри $[l,r)$, то строка $S[i..r)$ совпадает со строкой $S[i-l..r-l)$, и мы уже знаем её общий префикс с началом строки — это $z[i-l]$. Поэтому инициализируем $z[i] = \min(z[i-l],\ r-i)$ и расширяем дальше только в случае необходимости. Каждая успешная проверка во while сдвигает правую границу $r$, поэтому суммарно $O(n)$.
Для поиска подстроки склеиваем $S\ \#\ T$ и ищем позиции, где $z[i] = |S|$ (разделитель здесь даже необязателен, но для удобства можно оставить).
| Префикс-функция | Z-функция | |
|---|---|---|
| Определение | длина наибольшего бордера префикса | длина общего префикса с суффиксом |
| Добавление символа | позволяет (смотрим только «назад») | не позволяет (добавление в конец меняет все значения) |
| Простота | нужно думать про переходы по бордерам | взял наивный алгоритм и добавил $[l,r)$ |
Префикс-функция смотрит только на предыдущий префикс и добавляемый символ, поэтому её можно считать онлайн, добавляя символы по одному. Z-функция так не умеет.
Задача. Хранить множество слов с операциями «добавить», «удалить», «есть ли слово».
Идея. Слова, имеющие общий префикс, «схлопываются» — общий префикс хранится один раз. Получается корневое дерево, рёбра которого помечены символами.
cnt в вершине — сколько слов начинаются с этого префикса.Терминальная вершина — вершина, в которой заканчивается какое-то слово. При поиске идём по символам; если в конце терминальна — слово есть.
struct Node {
bool term = false;
unordered_map<char, Node*> next; // переходы (экономия памяти)
int cnt = 0; // сколько слов в поддереве
};
void add(Node* v, const string& s) {
for (char c : s) {
if (!v->next.count(c)) v->next[c] = new Node();
v = v->next[c];
v->cnt++; // слово проходит через v
}
v->term = true;
}
bool find(Node* v, const string& s) {
for (char c : s) {
if (!v->next.count(c)) return false;
v = v->next[c];
}
return v->term;
}Сложность всех операций — $O(\text{длина строки})$; суммарно по всем словам — $O(\text{сумма длин})$.
cnt (число слов в поддереве) позволяет отвечать «сколько слов начинаются с префикса $P$»: доходим до вершины, соответствующей $P$, и смотрим её cnt. При добавлении слова увеличиваем cnt на единицу на всём пути.Хранить детей: массивом размера алфавита (быстро, но ест память), map (медленно, $O(\log\sigma)$), unordered_map (средний случай $O(1)$, хеш-таблица) или списком пар (экономично, но перебор).
Задача. Дан массив чисел $y_1, \dots, y_n$; для каждого запроса $x$ найти $y_j$, дающее максимальный $x \oplus y_j$.
Идея. Запишем числа в двоичной системе (с ведущими нулями) и построим бор, где алфавит — $\{0, 1\}$.
Для запроса $x$ идём по битам от старшего к младшему и на каждом шаге жадно пытаемся пойти в ветку, противоположную текущему биту $x$ (чтобы в XOR получилась единица); если такой нет — идём в другую.
// максимальный x ^ y по всем y в боре
int max_xor(Node* v, int x) {
int res = 0;
for (int b = LOG - 1; b >= 0; --b) {
int bit = (x >> b) & 1;
int want = bit ^ 1; // хотим противоположный бит
if (v->next[want]) { // можем получить 1 в этом разряде
res |= (1 << b);
v = v->next[want];
} else {
v = v->next[bit];
}
}
return res;
}Аналогично находится $k$-е по возрастанию число: идём по битам, на каждом шаге смотрим cnt левой ветки — если $k \le cnt$ идём влево, иначе вычитаем $cnt$ и идём вправо. Сложность — $O(\log A)$ на запрос.
Вторая часть занятия — разбор контеста, который был по графам (не по строкам).
| Задача | Суть | Идея |
|---|---|---|
| B. Топсорт | проверить корректность топологической сортировки | для каждого ребра $u\to v$ проверить $\text{pos}[u] < \text{pos}[v]$ |
| C. КСС | компоненты сильной связности | стандартный алгоритм (Косарайю / Тарьян) |
| D. Кратчайший путь в DAG | кратчайший путь $S \to T$ | ДП по топсорту: $dp[v] = \min_{v\to u}(dp[u] + w)$ |
| E. Сумма длин всех путей | сумма по всем парам вершин дерева | вклад ребра = $w \cdot sz[v] \cdot (n - sz[v]) \cdot 2$ |
| F. Сумма путей из каждой вершины | для каждой вершины сумма расстояний до всех | rerooting: пересчёт ответа родителя в ответ сына |
| G. Делимость переменных | максимум различных значений | КСС → ответ $2\cdot(\#\text{КСС}) - (\#\text{КСС размера }1)$ |
| H. Детали | время изготовления детали №1 | DFS из 1 + топсорт + сумма времён |
| I. Монетка | минимизировать максимум чисел на пути из $k$ вершин | бинпоиск по ответу + цикл / длиннейший путь в DAG |
| J. Максимальный топсорт | лексикографически максимальный топсорт | обратная топсортировка со множеством/кучей |
| K. Пропуск | можно ли потерять пропуск | КСС по рёбрам 2-го типа + DFS по всем |
| L. Планарный граф | достижимость восточного берега | КСС + ДП min/max на конденсации |
Вместо суммирования по путям, суммируем по рёбрам: ребро с весом $w$, разбивающее дерево на части размеров $c_1$ и $c_2$, участвует в $c_1 \cdot c_2$ путях. Подвесим дерево; для ребра «родитель–сын $v$»:
Умножение на $2$ — потому что пути $u\to v$ и $v\to u$ считаются различными. $sz[v]$ считается DFS-ом за $O(n)$.
Сначала считаем $dp[v]$ — сумму длин путей от $v$ до всех вершин в её поддереве. Затем, зная ответ для родителя, пересчитываем ответ для ребёнка:
Идея: когда мы «переносим корень» через ребро $(parent, v)$, пути, ведущие не в поддерево $v$, удлиняются на $w$ (их $n - sz[v]$ штук), а пути внутрь поддерева $v$ укорачиваются на $w$ (их $sz[v]$ штук). Второй DFS проходит дерево и пересчитывает все ответы.
Факты «$x_i$ делится на $x_j$» дают ориентированный граф. Внутри цикла все значения обязаны совпадать по модулю (с точностью до знака) — значит, внутри каждой компоненты сильной связности значения равны с точностью до знака. В каждой КСС можно назначить два значения ($x$ и $-x$), кроме КСС размера 1 (там только одно).
Нужно минимизировать максимум значений на пути из $k$ вершин. Бинпоиск по ответу $x$: оставляем только вершины со значением $\le x$. В оставшемся графе ищем цикл — если есть, можно набрать сколько угодно вершин (ответ «да»); иначе это DAG, и достаточно найти длиннейший путь и сравнить его длину с $k$.
Чтобы лексикографически максимизировать порядок (первый элемент как можно больше, затем второй и т. д.), строим топсорт с начала: на каждом шаге из вершин без входящих рёбер (истоков) берём вершину с максимальным номером, ставим её следующей и удаляем из графа (уменьшая счётчики входящих степеней её соседей). Истоки поддерживаются в приоритетной очереди. Сложность $O((n+m)\log n)$. Если же в условии нужно максимизировать последний элемент, затем предпоследний и т. д., то порядок строят с конца: из стоков (вершин без исходящих рёбер) берут максимальную и ставят в конец; не путайте эти две постановки.
Рёбра двух видов: с пропуском и без. Строим КСС по рёбрам «без пропуска». Пропуск можно потерять, если существует вершина, достижимая из вершины $1$ (по всем рёбрам), чья компонента имеет исходящее ребро (по рёбрам «без пропуска»). Тогда оставляем пропуск в этой компоненте, выходим — и вернуться не сможем.