← к оглавлению
Строки — теория устных вопросов 18–22
Полиномиальное хеширование и Рабин-Карп, префикс-функция и КМП, бор, Ахо-Корасик, сжатые суффиксные ссылки. Формулировки — по лекциям курса.
18. Полиномиальное хеширование. Алгоритм Рабина — Карпа
Полиномиальный хеш
Для строки p[0:m]: hash(p) = (Σ p[i]·x^(m−1−i)) mod q, где q — простое, x ∈ [0, q). Считаем массив префиксных хешей, тогда хеш любой подстроки — за O(1): hash(p[l:r]) = (pₕ[r] − pₕ[l−1]·x^(r−l)) mod q.
Алгоритм Рабина — Карпа (поиск паттерна P в тексте T)
- Посчитать хеш паттерна за O(|P|).
- Посчитать префиксные хеши текста за O(|T|).
- Для каждой из O(|T|) подстрок длины |P| сравнить хеш с хешем P; при совпадении — проверить в лоб (защита от коллизии).
Вероятность коллизии ⩽ (|P|−1)/q. При q > |P|² среднее время O(|P| + |T|).
Спросят: как бороться с коллизиями (двойной хеш, прямое сравнение), выбор q и x, чувствительность к подбору (анти-хеш тесты).
▶ интерактив: повторяющиеся подстроки (хеши)
19. Префикс-функция. Алгоритм Кнута — Морриса — Пратта
Определения
Супрефикс строки S — строка, которая одновременно префикс и суффикс S.
Префикс-функция π[i] — длина максимального собственного (не равного всей строке) супрефикса строки S[:i].
Как считается
Ключевое: π[i+1] ⩽ π[i]+1. Если S[i+1]=S[π[i]] — π[i+1]=π[i]+1. Иначе перебираем кандидатов-супрефиксов в порядке вложенности π[i], π[π[i]−1], … пока не совпадёт символ или не дойдём до 0.
Время O(|S|) — амортизация: k растёт не более чем на 1 за шаг, значит суммарно уменьшается не больше |S| раз.
КМП (поиск P в T)
Строим строку S = P # T (# — символ не из алфавита), считаем π. Где π[i]=|P| — там конец вхождения P в T, добавляем в ответ позицию i−2|P| (с учётом #).
Спросят: доказать линейность (амортизационный анализ while), зачем разделитель #, связь с автоматом.
▶ интерактив: построение префикс-функции
20. Бор (trie) / префиксное дерево
Что это
Дерево, рёбра помечены символами; путь от корня до вершины — префикс. Терминальные вершины отмечают концы слов из набора. [u] — слово, читаемое по пути от корня до u.
Операции и память
- Вставка / поиск слова — за O(|слово|).
- Память — O(Σ|wᵢ|·|Σ|) при массиве переходов на вершину, или меньше при map.
Применение: словарь, поиск по префиксу, основа Ахо-Корасик.
Спросят: выбор контейнера переходов (массив vs map — память против скорости), терминальные пометки, обход бора.
21. Алгоритм Ахо — Корасик. Суффиксные ссылки. Автомат
Определения
Суффиксная ссылка link(u) — вершина v, где [v] — максимальный по длине суффикс [u], читаемый по бору от корня. Для корня — NIL.
Функция перехода: to(u,c) = vertex([u]+c), если из u есть переход по c; иначе to(link(u), c).
Соотношение: link(vertex([u]+c)) = to(link(u), c).
Построение
- Построить бор на наборе слов.
- BFS из корня насчитывает link и to(·,c): они выражаются через вершины выше по бору, база — корень.
Пересчёт link — O(1), всех to(·,c) для вершины — O(|Σ|), итого построение O(|Σ|·Σ|wᵢ|).
Суть: это ДКА, где состояния — вершины бора, принимающие — терминальные, начальное — корень, переход — to. По сути это обобщённая префикс-функция для набора строк (для одной строки суффиксные ссылки = позиции префикс-функции).
Спросят: почему BFS (нужны вышестоящие вершины), связь с префикс-функцией, что такое автомат Ахо-Корасик.
22. Сжатые суффиксные ссылки. Поиск множества паттернов в тексте
Проблема
При поиске идём по тексту функцией to за O(|T|); в каждой вершине прыгаем по суффиксным ссылкам до корня, считая терминальные. Число прыжков |jumps| может быть велико.
Сжатая ссылка
comp(u) = root, если u — корень; link(u), если link(u) терминальна; иначе comp(link(u)). Это первая терминальная вершина на пути суффиксных ссылок.
Прыгая по сжатым ссылкам, каждый прыжок либо даёт новое вхождение, либо ведёт в корень (и прыжки кончаются). Тогда |jumps| ⩽ 2·|ans|.
Итог поиска множества паттернов: O(|T| + |Σ|·Σ|Pᵢ| + |ans|).
Спросят: зачем сжатые ссылки (убрать лишние прыжки), оценка числа прыжков, сравнение с наивным запуском КМП по каждому паттерну.
Связка тем: префикс-функция (одна строка) → обобщается до автомата Ахо-Корасик (набор строк). Хеши (Рабин-Карп) — альтернатива для поиска подстрок и сравнения за O(1). Бор — структура-основа для Ахо-Корасик и словарей.