Сигнал задачи
Когда применять
Для поиска образцов и повторов в длинном тексте, сравнения множества подстрок или одновременного поиска словаря шаблонов.
Как выбрать подход
- KMP хранит длину совпавшего префикса шаблона и подходит для точного поиска одного шаблона без возврата по тексту.
- Z-функция измеряет совпадение каждого суффикса с префиксом; через строку «шаблон + разделитель + текст» она находит все вхождения.
- Rolling hash быстро сравнивает подстроки после подготовки, но равенство хешей вероятностно и при строгой корректности требует проверки или нескольких независимых модулей.
- Aho–Corasick строит trie с суффиксными ссылками и обрабатывает много шаблонов за один проход по тексту.
Сложность
- KMP и Z-функция: O(n + m) времени для текста длины n и шаблона длины m, память O(m) у KMP и O(n + m) у конкатенационного Z-поиска.
- Rolling hash: O(n) подготовка и память, O(1) на хеш подстроки; двоичный поиск длины добавляет множитель O(log n).
- Aho–Corasick с полной таблицей переходов: O(S · A) на построение и память, O(n + z) на поиск; разреженное хранение уменьшает память, но цена перехода зависит от контейнера. Здесь S — сумма длин шаблонов, A — алфавит, z — число вхождений.
Границы и ошибки
- Разделитель для Z-поиска не должен встречаться ни в шаблоне, ни в тексте.
- После полного совпадения KMP нужно продолжить с префикс-функции, иначе потеряются перекрывающиеся вхождения.
- Один rolling hash допускает коллизии; переполнение и нормализация отрицательных остатков зависят от языка.
- В Aho–Corasick нужно учитывать выходы по цепочке суффиксных ссылок и заранее оценивать память таблицы переходов.