Поиск по образцу: наивный алгоритм
P (длины M) в большом тексте T (длины N). Наивный (прямой) алгоритм прикладывает образец к каждой позиции текста. При первом несовпадении он делает возврат назад по тексту и сдвигает образец всего на 1 символ. Из-за таких возвратов худшее время работы равно O(N·M).
Поиск по образцу: постановка задачи
Задача поиска по образцу формулируется следующим образом: задан большой текст T (строка) длины N и некоторый короткий образец (паттерн) P длины M (где M <= N). Требуется найти первое (или все) вхождения образца P в текст T.
Эта задача является фундаментальной. На ее основе работают текстовые редакторы, поисковые системы, антивирусные сканеры (поиск сигнатур) и инструменты командной строки (например, утилита grep).
Прямой (наивный) алгоритм
Простейший метод решения заключается в последовательном прикладывании образца к тексту, начиная с первого символа. Мы сравниваем символы образца и текста слева направо. Если происходит несовпадение, мы "забываем" все уже прочитанные символы, сдвигаем образец вправо ровно на одну позицию и начинаем сравнение с начала образца.
Дальше весь модуль идет на одном примере: текст ABABADABABAC и образец ABABAC. Алфавит нарочно взят коротким - буквы A и B повторяются, поэтому окно раз за разом совпадает почти целиком и срывается на последнем символе. Рвет совпадение буква D: в образце ее нет вовсе, и в тексте она стоит ровно одна. На этом примере работают и схемы уроков, и тренажеры, так что цену каждого алгоритма можно сравнить напрямую.
#include <string.h>
/* Наивный поиск подстроки */
int naive_search(const char *text, const char *pattern) {
int n = strlen(text);
int m = strlen(pattern);
// Внешний цикл: прикладываем образец ко всем возможным позициям
for (int i = 0; i <= n - m; i++) {
int j;
// Внутренний цикл: сравниваем символы
for (j = 0; j < m; j++) {
if (text[i + j] != pattern[j]) {
break; /* Символы не совпали, прерываем проверку */
}
}
if (j == m) {
return i; /* Полное совпадение найдено, возвращаем индекс */
}
}
return -1; /* Совпадений нет */
}
ABABAC в тексте ABABADABABAC. Окно 0 совпадает на пяти символах из шести, и все пять сравнений приходится делать заново - на весь текст уходит 21 сравнение.Проблема наивного алгоритма
Главный недостаток наивного алгоритма - возврат назад по тексту. Если совпала большая часть образца, но последний символ оказался неверным, алгоритм не использует информацию о том, что эти первые символы только что успешно прошли проверку. Он делает шаг назад, сдвигает образец на единицу и начинает все с начала.
В худшем случае (например, когда текст состоит из "AAAAAAAAAB", а образец - "AAAB") алгоритм будет почти доходить до конца образца на каждом шаге и только на последнем символе понимать, что произошла ошибка. В таких случаях сложность алгоритма возрастает до O(N * M). Для решения этой проблемы были разработаны более эффективные алгоритмы со сложностью O(N + M), которые мы изучим в следующих уроках.
Тренажер: наивный поиск
Найдем образец ABABAC в тексте ABABADABABAC, прикладывая его к каждой позиции.
std::string::find() или функцией strstr() из языка Си. Часто это просто сильно оптимизированный наивный алгоритм, работающий очень быстро за счет векторизации и особенностей кэша процессора на коротких строках. В Python оператор in использует продвинутый алгоритм Бойера-Мура-Хорспула в сочетании с некоторыми эвристиками (FastSearch), избегая недостатков наивного подхода. Сам код выше написан на C, но собирается компилятором C++ без единой правки - как и все примеры этого модуля.
Коротко: главное
- Задача поиска по образцу - это нахождение всех вхождений короткого паттерна в длинный текст.
- Наивный алгоритм прикладывает образец к каждой позиции текста. При несовпадении он всегда сдвигается ровно на 1 символ вправо.
- Худшее время работы наивного алгоритма -
O(N * M)из-за возвратов по тексту.
Проверьте себя
В чем заключается главная архитектурная проблема наивного алгоритма поиска подстроки?