Поиск подстроки в строке — это важная задача в области алгоритмов обработки строк, которая требует эффективного нахождения вхождений одной строки (подстроки) в другую (основную строку). Существует несколько классических алгоритмов для решения этой задачи, каждый из которых оптимизирует различные аспекты поиска, такие как скорость, память и тип данных.
1. Алгоритм Кнута-Морриса-Пратта (KMP)
Описание: Алгоритм Кнута-Морриса-Пратта (KMP) использует метод предварительной обработки подстроки для построения массива префикс-функций. Эта информация позволяет избежать лишних сравнений, что делает поиск подстроки более эффективным.
Шаги алгоритма:
-
Строится префикс-функция для подстроки. Префикс-функция для символа в строке указывает на длину наибольшего префикса, который является также суффиксом.
-
Используя эту префикс-функцию, алгоритм сравнивает символы в основной строке с подстрокой, избегая возвратов назад и пропуская некоторые символы, если они уже были проверены.
Преимущества:
-
Время работы — O(n + m), где n — длина основной строки, а m — длина подстроки.
-
Алгоритм избегает повторных сравнений, что делает его гораздо быстрее простого поиска.
Потребление памяти:
- Дополнительная память для хранения префикс-функции — O(m).
Когда применять:
-
Когда необходимо множество поисков подстроки в одном тексте.
-
Когда важна высокая эффективность поиска, особенно для длинных строк и подстрок.
Префикс-функция — это ключевая концепция в алгоритмах обработки строк, особенно в алгоритме Кнута-Морриса-Пратта (KMP). Префикс-функция позволяет ускорить поиск подстроки, избегая повторных сравнений, и основана на анализе взаимосвязи между префиксами и суффиксами строки.
Определение
Префикс-функция для строки — это массив, который для каждой позиции в строке сохраняет длину наибольшего префикса, который является также суффиксом для подстроки, заканчивающейся в этой позиции.
Что такое префикс и суффикс?
-
Префикс строки — это любая начальная часть строки. Например, для строки “abcd” ее префиксами будут: "", “a”, “ab”, “abc”, “abcd”.
-
Суффикс строки — это любая конечная часть строки. Для строки “abcd” суффиксами будут: “abcd”, “bcd”, “cd”, “d”, "".
Пример
Возьмем строку “abacab”. Для этой строки префикс-функция будет выглядеть следующим образом:
-
Для первого символа: “a” — нет префикса, который является суффиксом, поэтому префикс-функция равна 0.
-
Для второго символа: “ab” — префикс “a” является суффиксом, поэтому значение префикс-функции для этого символа равно 1.
-
Для третьего символа: “aba” — префикс “a” является суффиксом, значение префикс-функции равно 1.
-
Для четвертого символа: “abac” — нет префикса, который является суффиксом, значение префикс-функции равно 0.
-
Для пятого символа: “abaca” — префикс “ab” является суффиксом, значение префикс-функции равно 2.
-
Для шестого символа: “abacab” — префикс “aba” является суффиксом, значение префикс-функции равно 3.
Префикс-функция для строки “abacab”: 0, 1, 1, 0, 2, 3
Зачем нужна префикс-функция?
-
Оптимизация поиска подстроки: позволяет избежать повторных сравнений в алгоритме Кнута-Морриса-Пратта, пропуская те части строки, которые уже были проверены.
-
Поиск повторяющихся подстрок: помогает быстро находить все вхождения повторяющихся подстрок в строке, анализируя общие префиксы и суффиксы.
2. Алгоритм Бойера-Мура
Описание: Алгоритм Бойера-Мура является одним из самых быстрых алгоритмов для поиска подстроки в строке в большинстве случаев. Он использует две основные идеи:
-
Пропускать символы в основной строке, если они не соответствуют текущему символу в подстроке.
-
Характеристики символов в подстроке позволяют сдвигать её значительно на большие расстояния.
Алгоритм Бойера-Мура работает по принципу поиска с конца подстроки, сравнивая её с текущей позицией в основной строке.
Шаги алгоритма:
-
Строятся два массива: неудачных сдвигов (bad character shift) и сдвигов для суффиксов (good suffix shift).
-
Процесс поиска заключается в сравнении символов с конца подстроки и сдвиге её на максимально возможное расстояние, когда сравнение неудачно.
Преимущества:
-
Время работы — в худшем случае O(n * m), но в среднем случае O(n / m), что намного быстрее стандартного алгоритма.
-
Пропускает большие блоки символов, если подстрока не совпадает с текстом.
Потребление памяти:
- Дополнительная память для массивов сдвигов — O(m).
Когда применять:
-
Для текстов с большим количеством символов и частыми несовпадениями.
-
Когда важна эффективность при сравнении больших подстрок с длинными текстами.
3. Алгоритм Рабина-Карпа
Описание: Алгоритм Рабина-Карпа использует метод хеширования для поиска подстроки в строке. Вместо того, чтобы поочередно сравнивать символы подстроки с основной строкой, алгоритм сначала вычисляет хеш-код для подстроки и для всех подстрок основной строки того же размера. Если хеш-коды совпадают, то выполняется сравнение символов для проверки совпадения.
Шаги алгоритма:
-
Вычисляется хеш подстроки.
-
Вычисляются хеши всех возможных подстрок основной строки с тем же размером.
-
Если хеши совпадают, то выполняется проверка символов на совпадение.
Преимущества:
-
Время работы в худшем случае — O(n * m), но для хороших хеш-функций в среднем случае время работы составляет O(n + m).
-
Прост в реализации и широко применяется для поиска нескольких вхождений подстрок в строку.
Потребление памяти:
- Дополнительная память для хранения хешей — O(n).
Когда применять:
-
Для поиска подстроки в большом тексте, когда важно искать сразу несколько вхождений подстроки.
-
Когда можно использовать хорошие хеш-функции для минимизации вероятности коллизий.
Сравнение алгоритмов
| Алгоритм | Время работы в худшем случае | Время работы в среднем случае | Память | Применимость |
|---|---|---|---|---|
| KMP | O(n + m) | O(n + m) | O(m) | Для быстрого поиска подстроки с высокой производительностью. |
| Бойер-Мур | O(n * m) | O(n / m) | O(m) | Для эффективного поиска в больших строках, когда текст длинный и много несовпадений. |
| Рабин-Карп | O(n * m) | O(n + m) | O(n) | Для поиска нескольких вхождений подстроки или когда можно использовать хеширование. |
Когда какой алгоритм использовать?
-
KMP — когда важна стабильная производительность и отсутствие лишних сравнений.
-
Бойер-Мур — когда подстрока и текст большие, и требуется высокая производительность за счет пропуска символов.
-
Рабин-Карп — когда нужно искать несколько подстрок или работать с большими текстами с использованием хеширования.