Дана строка text длины n и строка pattern длины m. Найти все вхождения pattern в text.
n ≤ 106, m ≤ 106. Лимит: 1 сек.
Пример:
text = "abcabcabc"
pattern = "abc"
Ответ: позиции 0, 3, 6
Как бы вы решили эту задачу?
Наивный подход: O(n·m)
for (int i = 0; i + m <= n; i++) {
bool match = true;
for (int j = 0; j < m; j++) {
if (text[i + j] != pattern[j]) {
match = false;
break;
}
}
if (match) cout << i << "\n";
}
Плохой случай:
text = "aaaaaaaaa..." (106 символов 'a')
pattern = "aaaa...ab" (106 - 1 символ 'a' + 'b')
Каждая позиция сравнивает почти m символов → TLE
При n = m = 106 это ~1012 операций. Нужен алгоритм за O(n + m).
Хеш-функция: строка → число
Вместо посимвольного сравнения двух строк — сравниваем их числовые отпечатки (хеши)
Если хеши разные → строки точно разные
Если хеши одинаковые → строки скорее всего одинаковые (маленькая вероятность ошибки)
Как отпечатки пальцев: если отпечатки не совпали — точно разные люди. Если совпали — скорее всего один и тот же человек (но в теории возможна ошибка).
Для проверки «подстрока text[i..i+m-1] == pattern»:
hash(s[l..r]) = h[r+1] - h[l] · pw[r-l+1] (mod M)
На олимпиаде проще всего использовать вариант со степенями, убывающими слева направо.
Формула для подстроки: h[r+1] - h[l] · pw[r-l+1]
Предвычисление хешей и степеней
const long long MOD = 1e9 + 7;
const long long P = 31;
// Предвычисляем степени p
vector<long long> pw(n + 1);
pw[0] = 1;
for (int i = 1; i <= n; i++)
pw[i] = pw[i - 1] * P % MOD;
// Предвычисляем префиксные хеши текста
// h[i] = hash первых i символов (степени убывают)
vector<long long> h(n + 1, 0);
for (int i = 0; i < n; i++)
h[i + 1] = (h[i] * P + (text[i] - 'a' + 1)) % MOD;
Пояснение: h[i+1] = h[i] · p + code(text[i])
Каждый новый символ «сдвигает» предыдущий хеш влево (умножает на p) и добавляет свой код
Сложность: O(n) — один проход
Получение хеша подстроки
// Хеш подстроки text[l..r] (0-indexed, включительно)
long long get_hash(int l, int r) {
return (h[r + 1] - h[l] * pw[r - l + 1] % MOD + MOD) % MOD;
}
Разбор формулы:
h[r+1] содержит хеш text[0..r]
h[l] · pw[r-l+1] — «сдвигает» хеш text[0..l-1]
Разность даёт хеш text[l..r]
+ MOD — чтобы результат не был отрицательным
text: a b c a b c
h: [0][h1][h2][h3][h4][h5][h6]
hash("cab") = hash(text[2..4]) = h[5] - h[2] * pw[3]
Поиск подстроки: полный код
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const long long P = 31;
int main() {
string text, pattern;
cin >> text >> pattern;
int n = text.size(), m = pattern.size();
vector<long long> pw(max(n, m) + 1);
pw[0] = 1;
for (int i = 1; i <= max(n, m); i++)
pw[i] = pw[i - 1] * P % MOD;
vector<long long> h(n + 1, 0);
for (int i = 0; i < n; i++)
h[i + 1] = (h[i] * P + (text[i] - 'a' + 1)) % MOD;
long long h_pat = 0;
for (int i = 0; i < m; i++)
h_pat = (h_pat * P + (pattern[i] - 'a' + 1)) % MOD;
for (int i = 0; i + m <= n; i++) {
long long h_sub = (h[i + m] - h[i] * pw[m] % MOD + MOD) % MOD;
if (h_sub == h_pat)
cout << i << "\n";
}
return 0;
}
Сложность: O(n + m) — сравнение за O(1) вместо O(m)
Коллизии: когда хеш врёт
Проблема:
Хеш отображает ∞ строк в {0, 1, ..., M-1}
По принципу Дирихле: существуют разные строки с одинаковым хешем
Одно сравнение: вероятность коллизии ~1/M ≈ 10-9
~106 сравнений: вероятность ≥ 1 коллизии ~10-3 (парадокс дней рождения!)
const long long MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;
const long long P1 = 31, P2 = 37;
struct Hash {
long long h1, h2;
bool operator==(const Hash& o) const {
return h1 == o.h1 && h2 == o.h2;
}
};
// Предвычисляем два массива хешей h1[], h2[]
// и два массива степеней pw1[], pw2[]
Hash get_hash(int l, int r) {
long long v1 = (h1[r+1] - h1[l] * pw1[r-l+1] % MOD1 + MOD1) % MOD1;
long long v2 = (h2[r+1] - h2[l] * pw2[r-l+1] % MOD2 + MOD2) % MOD2;
return {v1, v2};
}
На большинстве олимпиадных задач одного хеша достаточно. Двойной хеш — для надёжности на сложных тестах.
Частые баги при хешировании
'a' → 0: Если 'a' = 0, то "a", "aa", "aaa" дают хеш 0 Решение: используйте s[i] - 'a' + 1
Отрицательный остаток:h[r+1] - h[l] * pw[...] может быть < 0 Решение: + MOD) % MOD
Переполнение:h[l] * pw[...] переполняет long long до взятия MOD Решение: промежуточный % MOD — h[l] * pw[...] % MOD
Забыли предвычислить степени: pw[i] нужен заранее Решение: массив pw[] в начале
Если получаете WA с хешами — сначала проверьте эти 4 пункта
Где ещё полезен хеш?
Поиск подстроки — то, что мы разобрали (O(n + m))
Количество различных подстрок длины k — хеши в set (O(n))
Наибольшая общая подстрока — бинпоиск по длине + хеш (O(n log n))
Палиндромы — сравнить хеш подстроки с реверсом (O(1))
Сравнение подстрок на равенство — O(1) вместо O(длина)
Хеширование позволяет сравнивать строки за O(1) после O(n) предвычисления. Это основной инструмент.
Задача: различные подстроки длины k
Дана строка s длины n и число k. Посчитать количество различных подстрок длины k.
n ≤ 105, 1 ≤ k ≤ n.
Идея решения:
Предвычислить хеши строки s
Для каждой позиции i от 0 до n-k: вычислить хеш s[i..i+k-1]
Добавить все хеши в set<long long>
Ответ = размер множества
Сложность: O(n log n) с set, O(n) с unordered_set
Практика: 15 минут
⭐ Базовая: Реализуйте поиск всех вхождений pattern в text с помощью хеширования (напишите сами, не копируйте)
⭐⭐ Средняя: Посчитайте количество различных подстрок длины k
⭐⭐⭐ Сложная: Для каждого l от 1 до n определить, есть ли повторяющаяся подстрока длины l
Я хожу по классу — задавайте вопросы!
Разбор
Средняя задача — решение:
set<long long> distinct;
for (int i = 0; i + k <= n; i++) {
long long hash_sub = (h[i + k] - h[i] * pw[k] % MOD + MOD) % MOD;
distinct.insert(hash_sub);
}
cout << distinct.size() << "\n";
Ключевые моменты:
Формула хеша подстроки — та же, что на слайде 2.6
Не забываем + MOD
set гарантирует уникальность
Кто решил? Какие ошибки были?
Хеш — это здорово, но...
Минусы хеша:
Вероятность ошибки (коллизии)
«Антихеш-тесты» ломают одинарный хеш
Двойной хеш — удваивается код
Альтернатива: Z-функция
Точное решение (без коллизий)
O(n + m) — такая же сложность
Один массив, один проход
Но чуть сложнее для понимания
Z-функция: определение
Z-функция строки s — это массив z[], где z[i] = длина наибольшего общего префикса строки s и подстроки s[i..n-1].
Другими словами: z[i] — сколько символов, начиная с позиции i, совпадают с началом строки.
z[0] не определяется (обычно z[0] = 0 или z[0] = n)
Пример:
s = a a b a a b a a
i = 0 1 2 3 4 5 6 7
z[i] = - 1 0 5 1 0 2 1
Пояснение: z[3] = 5
s[3..7] = "aabaa"
s[0..4] = "aabaa"
Совпадают 5 символов → z[3] = 5
Трюк: pattern + "$" + text
Идея:
Склеиваем: t = pattern + "$" + text ($ — разделитель)
Вычисляем Z-функцию строки t
Если z[i] == m → вхождение pattern на позиции i - m - 1 в text
Визуализация:
pattern = "ab", text = "ababab"
t = "ab$ababab"
z = [- 0 0 2 0 2 0 2 0]
^ ^ ^
z[3]=2 z[5]=2 z[7]=2 ← все вхождения pattern!
Позиции в text: i - m - 1 = {0, 2, 4}
Наивный алгоритм: O(n²)
vector<int> z(n, 0);
for (int i = 1; i < n; i++) {
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
z[i]++;
}
Для каждого i посимвольно сравниваем s[i+0] с s[0], s[i+1] с s[1], ...
Сложность: O(n²) в худшем случае (строка из одинаковых символов)
Как ускорить до O(n)?
Идея: окно [l, r]
Ключевое наблюдение:
Вычислив z[i], мы знаем: s[i..i+z[i]-1] == s[0..z[i]-1]
Подстрока [i, i+z[i]-1] — «копия» начала строки
Запоминаем самый правый такой отрезок: [l, r]
s: [========================]
[l.......r] ← s[l..r] == s[0..r-l]
^i
мы знаем, что s[i] == s[i-l]
значит z[i] >= z[i-l] (но не больше r-i+1!)
Два случая для позиции i:
i > r: ничего не знаем → наивно считаем z[i]
i ≤ r: z[i] ≥ min(z[i-l], r-i+1). Дальше — докручиваем наивно
Z-функция за O(n): код
vector<int> z_function(const string& s) {
int n = s.size();
vector<int> z(n, 0);
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;
}
if (i < r) — используем ранее вычисленную информацию
while (...) — докручиваем наивно (но суммарно O(n))
if (i + z[i] > r) — обновляем самый правый блок
Сложность: O(n)
Пример: Z-функция "aabxaab"
s: a a b x a a b
i: 0 1 2 3 4 5 6
i
l
r
Начальное z[i]
После while
z[i]
1
0
0
0 (i≥r)
s[0]='a'==s[1]='a', s[1]='a'≠s[2]='b'
1
2
1
2
0 (i≥r)
s[0]='a'≠s[2]='b'
0
3
1
2
0 (i≥r)
s[0]='a'≠s[3]='x'
0
4
1
2
0 (i≥r)
'a'=='a', 'a'=='a', 'b'=='b', конец
3
5
4
7
min(2, z[1])=1
s[1]='a'≠s[6]='b'
1
6
4
7
min(1, z[2])=0
s[0]='a'≠s[6]='b'
0
Результат: z = [-, 1, 0, 0, 3, 1, 0]
Поиск подстроки: Z-функция
#include <bits/stdc++.h>
using namespace std;
vector<int> z_function(const string& s) {
int n = s.size();
vector<int> z(n, 0);
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;
}
int main() {
string text, pattern;
cin >> text >> pattern;
int m = pattern.size();
string t = pattern + "$" + text;
vector<int> z = z_function(t);
for (int i = m + 1; i < (int)t.size(); i++)
if (z[i] == m)
cout << i - m - 1 << "\n";
return 0;
}
Сложность: O(n + m) — точное решение, без коллизий
Сравнение: хеш vs Z-функция
Хеширование
Z-функция
Точность
Вероятность коллизии (мала)
Точно
Сложность
O(n + m)
O(n + m)
Гибкость
Хеш любой подстроки за O(1)
Только сравнение с префиксом
Применение
Произвольные подстроки, различные подстроки
Поиск паттерна, период строки
Длина кода
Короче (двойной — длиннее)
Средняя
Хеш — когда нужно сравнивать произвольные подстроки между собой. Z-функция — когда нужно сравнивать подстроки с началом строки (или с паттерном).
Период строки
Строка s имеет период длины p, если s[i] == s[i + p] для всех допустимых i.
Пример: "abcabcabc" имеет период 3 ("abc" повторяется).
Через Z-функцию:
p — период ⇔ z[p] ≥ n - p (и n % p == 0 для полного совпадения)
Минимальный период: наименьшее p, при котором z[p] == n - p и n % p == 0
vector<int> z = z_function(s);
int period = n;
for (int p = 1; p < n; p++) {
if (z[p] == n - p && n % p == 0) {
period = p;
break;
}
}
Практика: 10 минут
⭐ Базовая: Реализуйте поиск всех вхождений pattern в text через Z-функцию (напишите сами)
⭐⭐ Средняя: Найдите минимальный период строки
⭐⭐⭐ Для размышления: CF 126B «Password» — строка, которая является одновременно префиксом, суффиксом, и встречается в середине
Я хожу по классу — задавайте вопросы!
Разбор
CF 126B — подсказка к решению:
Суффикс = префикс: z[i] == n - i → s[i..n-1] = s[0..n-i-1]
Среди всех таких суффиксов: найти тот, длина которого (n-i) встречается как z[j] для j в середине
Берём наибольший такой суффикс
Кто решил базовую? У кого какие вопросы?
Задача 126B — красивая, попробуйте дорешать дома!
Что мы изучили сегодня
Хеширование строк:
Полиномиальный хеш: hash(s) = Σ s[i]·pi (mod M)
Хеш подстроки за O(1) через префиксные хеши
Двойной хеш для надёжности
Универсальный инструмент для сравнения строк
Z-функция:
z[i] = длина общего префикса s и s[i..]
Вычисление за O(n) с окном [l, r]
Поиск подстроки: pattern + "$" + text
Период строки, суффикс=префикс
Обе техники решают поиск подстроки за O(n + m)
Домашняя практика
Поиск подстроки (хеш или Z) — CSES «String Matching»
Различные подстроки (хеш) — eolymp 2356 «Substrings»
Период строки (Z) — CF 182D «Common Divisors» или CSES «Finding Periods»
CF 126B «Password» (Z) — префикс = суффикс в середине
CF 271D «Good Substrings» (хеш) — подсчёт подстрок с условием
Завтра: Euler tour и LCA — строки пригодятся на финальном контесте!