Алгоритмы
Поиск подстроки: Введение
Цели урока
- Понять задачу поиска подстроки
- Реализовать наивный алгоритм
- Понимать его слабости
- Знать идеи улучшенных алгоритмов
Предварительные знания
- Big O нотация
Каждый раз, когда вы нажимаете Ctrl+F, за кулисами работает один из самых отточенных алгоритмов. Как найти иголку в стоге сена размером в гигабайты за миллисекунды?
- Текстовые редакторы и IDE
- grep, awk и другие Unix-утилиты
- Поисковые системы
- Биоинформатика (секвенирование ДНК)
Наивный перебор и гонка за его улучшение
Поиск одной строки внутри другой, это одна из старейших задач в программировании. Она нужна в текстовых редакторах, компиляторах и поиске с 1960-х. Очевидный метод сдвигает шаблон на один символ и сравнивает: просто, но в худшем случае делает около n на m сравнений, например при поиске aaab в длинной цепочке символов a. Долгое время считали, что эта квадратичная стоимость для общего перебора неизбежна. Прорыв случился около 1970 года, когда Джеймс Моррис и Воган Пратт, а Дональд Кнут дал формальный анализ, показали, что поиск можно выполнить за линейное время, запоминая, что шаблон уже сопоставил. Эта работа, опубликованная в 1977 году, стала алгоритмом KMP и открыла десятилетие быстрого поиска строк, куда входят Бойер-Мур и Рабин-Карп.
Задача поиска подстроки
**Задача:** найти все вхождения паттерна P в тексте T.
**Применения:**
- **Текстовые редакторы:** Ctrl+F, Find & Replace
- **Биоинформатика:** поиск генов в ДНК
- **Антивирусы:** поиск сигнатур вирусов
- **Сетевые фильтры:** поиск паттернов в трафике
| Обозначение | Значение |
|---|---|
| n | Длина текста T |
| m | Длина паттерна P |
| Σ | Алфавит (набор символов) |
Сколько вхождений "ABA" в "ABABABA"?
Наивный алгоритм
| Случай | Сложность | Пример |
|---|---|---|
| Best | O(n) | Нет совпадений, первый символ разный |
| Average | O(n) | Случайный текст и паттерн |
| Worst | O(n×m) | T = "AAA...A", P = "AAA...AB" |
**Проблема:** при несовпадении мы «забываем» всё, что узнали о тексте, и начинаем заново.
T = "AAAAA" (5 A), P = "AA". Наивный алгоритм сделает сравнений:
Идея улучшения
**Ключевое наблюдение:** при несовпадении мы уже знаем часть текста!
**Два подхода к улучшению:**
| Алгоритм | Идея | Сложность |
|---|---|---|
| KMP | Предвычисляем «откаты» в паттерне | O(n + m) |
| Rabin-Karp | Хеширование: сравниваем хеши, не строки | O(n + m) avg |
| Boyer-Moore | Ищем с конца, прыгаем далеко | O(n/m) best! |
| Z-функция | Предвычисляем префиксы | O(n + m) |
**На практике:** Boyer-Moore часто быстрее для длинных паттернов (grep использует его). KMP гарантирует O(n+m) в худшем случае.
Можно ли искать подстроку быстрее O(n)?
Поиск подстроки
- Задача: найти P в T
- Наивный: O(n×m) в худшем случае
- Проблема: забываем информацию при откате
- Решения: KMP, Rabin-Karp, Boyer-Moore
- Все дают O(n+m) или лучше
Связанные темы
Поиск подстроки - основа для многих алгоритмов.
- KMP — O(n+m) через prefix function
- Rabin-Karp — O(n+m) через хеширование
Связанные уроки
- alg-24-kmp — KMP улучшает наивный поиск до гарантированного O(n+m)
- alg-25-rabin-karp — Rabin-Karp ускоряет поиск через скользящие хеши
- alg-01-big-o — Сравнение O(nm) и O(n+m) требует анализа сложности
- ds-13-trie — Trie ищет много паттернов сразу по тексту
- comp-07-regex-in-lexer