Алгоритмы
KMP: Кнут-Моррис-Пратт
Цели урока
- Понять идею KMP
- Вычислять prefix function
- Реализовать KMP поиск
- Применять для периодов и ротаций
Предварительные знания
- Наивный поиск подстроки
В 1977 году Кнут, Моррис и Пратт опубликовали алгоритм, который гарантирует O(n+m) для поиска подстроки. Никаких откатов в тексте - каждый символ смотрим максимум дважды!
- grep с фиксированными паттернами
- Биоинформатика
- Текстовые редакторы
- Компиляторы (лексический анализ)
Три человека, один линейный поиск
У алгоритма KMP необычное происхождение: его открыли дважды и затем объединили. В 1970 году Джеймс Моррис писал текстовый редактор, и ему был нужен поиск строки, который никогда не откатывает указатель входа, чтобы редактор мог обрабатывать символы потоком. Он сам вывел префикс-функцию. Примерно в то же время Дональд Кнут изучал теорему Стивена Кука о двусторонних магазинных автоматах и вывел, что линейный поиск строки должен существовать, а затем построил его. Воган Пратт связал две линии работы. Втроём они опубликовали результат в 1977 году под названием Fast Pattern Matching in Strings. Сердце метода, это префикс-функция, вычисляемая один раз по шаблону: при несовпадении она говорит, насколько можно сдвинуть шаблон без повторной проверки символов, что даёт суммарное время O(n + m).
Идея: не откатываться в тексте
**Главная идея KMP:** при несовпадении мы уже знаем часть текста (она совпала с началом паттерна). Используем это!
**Ключ:** prefix function π[j] говорит, куда прыгнуть в паттерне при несовпадении.
В KMP указатель i (по тексту):
Prefix function (pi)
**Prefix function π[i]** - длина наибольшего собственного префикса строки P[0:i+1], который также является суффиксом.
**Почему O(m)?** k увеличивается максимум m раз (по одному на итерацию), а уменьшается только когда было увеличение. Суммарно ≤ 2m операций.
π для "ABCABC" на позиции 5 (последний C)?
Реализация KMP
| Операция | Сложность |
|---|---|
| Prefix function | O(m) |
| Поиск | O(n) |
| Итого | O(n + m) |
**Память:** O(m) для prefix function. Это лучше, чем O(n×m) для некоторых других алгоритмов.
После полного совпадения (j=m), почему j = π[m-1], а не j = 0?
Применения
**1. Проверка циклического сдвига:**
**2. Подсчёт вхождений:**
**3. Период строки:**
**Z-функция** - альтернатива prefix function. Z[i] = длина наибольшего префикса, начинающегося с i. Тоже O(n+m).
Как проверить, что строка - это k повторений некоторого паттерна?
KMP алгоритм
- Prefix function π[i] = макс. префикс = суффикс
- При несовпадении j = π[j-1], i не меняется
- O(n + m) время, O(m) память
- Находит перекрывающиеся вхождения
- Бонус: период строки за O(n)
Связанные темы
KMP - один из классических алгоритмов поиска.
- Rabin-Karp — Альтернатива через хеширование
- Z-функция — Альтернативная предобработка
Связанные уроки
- alg-23-pattern-matching — KMP - оптимизированный ответ на наивный поиск подстроки
- alg-40-z-function — Z-функция строит похожую префиксную структуру линейно
- alg-25-rabin-karp — Оба дают O(n+m); KMP детерминирован, RK хеширует
- dm-15 — Префикс-функция кодирует конечный автомат по паттерну
- nlp-01