Алгоритмы поиска подстроки

Задача поиска подстроки: для текста T длины n и образца P длины m требуется найти все позиции i (0-индексация), такие что T[i..i+m−1] = P.

Ключевые применения: поиск ключевых слов, фильтрация логов, анализ ДНК-цепочек, подсветка совпадений, предобработка в компиляторах. В заданиях ЕГЭ по информатике встречаются задачи на подсчёт вхождений, проверку наличия/позиции, поиск с различными ограничениями на алфавит/регистр, а также вопросы по асимптотике.

Формальная модель

• Текст: T = T[0] T[1] … T[n−1], алфавит Σ.
• Образец: P = P[0] P[1] … P[m−1].
• Множество решений:
  Occ(P, T) = { i | 0 ≤ i ≤ n−m,  ∀k∈[0..m−1]: T[i+k] = P[k] }.

• Сложность оценивается по числу сравнений символов и вспомогательным операциям (хеши, переходы).

Нижняя оценка: любая корректная процедура в худшем случае смотрит Ω(n) символов, если m фиксировано и P нетривиален.

Наивный алгоритм: базовая точка отсчёта

1. Идея
   

   Сдвигаем окно длины m по T и сравниваем символы.

   для i = 0..n−m:

       проверить равенство T[i..i+m−1] и P[0..m−1]

   Сравнение обычно выполняется справа налево или слева направо; останов при первом несовпадении.

2. Корректность и сложность
   

   • Корректность очевидна: анализируем все возможные выравнивания.

   • Сложность: O(n·m) в худшем случае (например, T = aaaa…ab, P = aaaa…ac).

   Где полезен: очень короткие m, маленькие тексты, когда накладные расходы на предобработку критичнее.

Алгоритм Кнута–Морриса–Пратта (КМП)

1. Интуиция
   

   КМП избегает повторного сравнения ранее совпавших префиксов. При несоответствии на позиции j в образце, окно сдвигается на величину, определённую функцией наибольшего собственного префикса, являющегося суффиксом (π-функция).

2. Префикс-функция (π)
   

   Для строки S длины L:

   π[0] = 0

   π[i] = длина наибольшего собственного префикса S[0..i], совпадающего с суффиксом S[0..i]

   Стандартная линейная конструкция π требует O(L) времени.

   Для поиска π строится по P, после чего выполняется линейный проход по T, поддерживая длину текущего совпадения q с префиксом P[0..q−1].

3. Поиск (схема)
   

   q = 0

   для i = 0..n−1:

       пока q > 0 и P[q] ≠ T[i]:

           q = π[q−1]

       если P[q] = T[i]:

           q++

       если q = m:

           зафиксировать вхождение i−m+1

           q = π[m−1]

4. Инварианты и сложность
   

   • Инвариант: в любой момент q – длина максимального префикса P, совпадающего с суффиксом T[0..i].

   • Сложность: O(n + m) по времени, O(m) памяти.

   Практика: устойчив к «злонамеренным» примерам, хорош, когда нужно гарантированное линейное время.

Рабин–Карп: хеширование и окна

1.  Идея
   

   Сопоставлять не символы, а хеши окон T[i..i+m−1], поддерживая rolling hash. Совпадение хеша → проверка посимвольно (чтобы исключить коллизию).

2. Полиномиальный хеш
   

   Для строки S:

   H(S) = ( Σ_{k=0..|S|−1} S[k] · p^k ) mod M

   Рекомендуется большой модуль M и основание p. При скользящем окне выполняется:

   H_next = ( (H_current − S_out · p^{m−1}) · p + S_in ) mod M

3.  Сложность и вероятности
   

   • Ожидаемая сложность: O(n + m) при малом числе ложных совпадений, худший случай O(n·m), если хеш часто совпадает.

   • Вероятность ложного совпадения ≈ 1/M при «хорошем» выборе параметров.

   Практика: эффективен для множественных образцов (поиск многих P_i одновременно), для потоков, когда удобно работать с числами.

Бойер–Мур: эвристики «плохого символа» и «хорошего суффикса»

1. Идея
   

   Сравнение выполняется справа налево; при первом несовпадении образец сдвигается сразу на много позиций по заранее вычисленным таблицам.

2. Плохой символ (bad character)
   

   Таблица Bad[c] – позиция последнего вхождения символа c в P (или −1). Если несовпадение на P[j] и T[i] = c, то возможный сдвиг:

   shift_bad = j − Bad[c]

   (не меньше 1).

3.  Хороший суффикс (good suffix)
   

   Если совпал суффикс P[j+1..m−1], таблица Good[j] даёт сдвиг так, чтобы выровнять в P другое вхождение этого суффикса или, если его нет, совпадающий префикс.

4.  Сложность
   

   • Ожидаемо очень быстро на «случайных» текстах: подстрока перескакивает большие фрагменты → близко к O(n/m) сравнений.

   • В худшем случае O(n·m) (например, повторяющиеся символы).

   • Варианты BM (Boyer–Moore–Horspool, Sunday) упрощают таблицы и практично ускоряют средний случай.

   Практика: высокопроизводителен при большом алфавите и случайных данных; хорош для прикладных поисков в файлах/логах.

Z-функция и π-функция: линейные префиксные техники

1. Z-функция
   

   Для S:

   Z[i] = длина наибольшего префикса S, совпадающего с S[i..]

   Строится за O(|S|). Для поиска подстроки рассматривают строку:

   S = P + '#' + T

   Позиции, где Z[i] = m, соответствуют вхождениям P в T.

2. π-функция (альтернатива КМП)
   

   Можно так же конкатенировать P#T и вычислить π; значения π[i] = m указывают на вхождения. Обе техники линейны и просты в коде.

Сравнение алгоритмов

*При хорошо подобранных параметрах ожидаемо линейный.

Инженерные правила (чек-лист)

R1  Если нужна гарантия линейного времени и простота – выбирайте КМП или Z/π.

R2  Для очень больших текстов и «обычных» данных – Бойер–Мур(Хорспул/Санди) даст лучший средний случай.

R3  Для множественного поиска (много образцов) используйте Рабина–Карпа или автоматы (Ахо–Корасик).

R4  В Рабине–Карпе всегда подтверждайте совпадение посимвольно (антиколлизия).

R5  Учитывайте алфавит: для маленького алфавита BM теряет эффективность из-за частых «плохих символов».

R6  Следите за границами массивов таблиц (Bad/Good/π/Z), не выходите за пределы.

R7  Для чувствительности/нечувствительности к регистру нормализуйте вход (например, к нижнему регистру).

R8  Для Юникода используйте сравнение по кодопойнтам, не по байтам UTF-8 без осознания границ символов.

R9  В задачах ЕГЭ заранее оцените `n`, `m` и алфавит – это подскажет оптимальный метод.

R10 Отлаживайте на «злых» случаях: одинаковые символы, периодические строки, очень длинные совпадения с сбоем в конце.

Типичные ошибки и анти-паттерны

1. Неверная инициализация π/Z → пропуск вхождений.
2. Отсутствие проверки при совпадении хеша в Рабине–Карпе → ложноположительные ответы.
3. Неправильные сдвиги в Бойере–Муре (отрицательный или нулевой сдвиг) → зацикливание.
4. Сравнение байтов UTF-8 вместо символов → разрывы мультибайтовых кодов.
5. Несогласованность индексации (0/1) при формировании ответов → «съехавшие» позиции.

Мини-шпаргалка 

Префикс-функция π для S:

π[0] = 0

для i=1..|S|−1:

    j = π[i−1]

    пока j>0 и S[i] ≠ S[j]: j = π[j−1]

    если S[i] = S[j]: j++

    π[i] = j 

КМП-поиск P в T:

q = 0

для i=0..n−1:

    пока q>0 и P[q] ≠ T[i]: q = π[q−1]

    если P[q] = T[i]: q++

    если q = m: ответ (i−m+1), q = π[m−1] 

Полиномиальный хеш (rolling):

H_next = ( (H − out·p^{m−1})·p + in ) mod M 

Сдвиг «плохого символа»:

shift_bad = max(1, j − Bad[T[i]]) 

Связь с ЕГЭ по информатике

• Алгоритмизация: построение линейных решений (КМП/Z), аккуратная работа с массивами.
• Строки: подсчёт вхождений, поиск первого/всех совпадений, анализ асимптотики.
• Теория вычислений: доказательство корректности через инварианты префиксов/суффиксов.
• Оценка сложности: выбор алгоритма по n, m, Σ, анализ худшего/среднего случая.

Пять упражнений 

Упражнение 1. Построение π-функции и КМП

Даны T и P.
a) Постройте π для P и выведите массив π в явном виде.
b) Используя схему КМП, найдите все позиции вхождений P в T.
c) Докажите, что суммарное число сравнений символов не превышает 2n (до константы).

Упражнение 2. Рабин–Карп: параметры и ложные совпадения

Для фиксированных M и p реализуйте rolling hash.
a) Оцените вероятность ложного совпадения как ≈ 1/M.
b) Подберите M (простое число) так, чтобы вероятность была < 10^{-9}.
c) На случайном тексте оцените ожидаемое число ложных совпадений и подтвердите, что итоговая сложность близка к O(n).

Упражнение 3. Бойер–Мур–Хорспул

Реализуйте BM-Horspool (только «плохой символ» по последнему символу окна).
a) Постройте таблицу сдвигов длиной |Σ|.
b) На текстах из латиницы сравните время с наивным алгоритмом и КМП для m=8, 32, 128.
c) Объясните, почему на случайных текстах BM-Horspool выигрывает, а на малом алфавите – нет.

Упражнение 4. Z-функция для конкатенации

Постройте строку S = P#T.
a) Постройте массив Z.
b) Выведите все позиции i, для которых Z[i] = m; это вхождения P в T.
c) Сравните затраты памяти и времени с КМП; объясните эквивалентность результатов.

Упражнение 5. Периодичность строки и поиск

Пусть образец P имеет период d, т. е. P[i] = P[i−d] для всех допустимых i.
a) Докажите, что m − π[m−1] равен минимальному периоду d_min.
b) Объясните, как знание периода сокращает число сдвигов в КМП.
c) Для P = "abababababa" вычислите π и укажите d_min.

Практические рекомендации и гигиена кода

• Изолируйте предобработку (π/Z/таблицы BM) от основного поиска; пишите модульные тесты именно на предобработку.
• Для больших T/P используйте 0-индексацию и явные типы длин (size_t, 64-битные).
• В текстах с Unicode нормализуйте форму (NFC/NFD) перед поиском, если важна лингвистическая корректность.
• Для чувствительности/нечувствительности к регистру – заранее приведите T и P к одной форме.
• Профилируйте: практическая производительность BM-семейства зависит от распределения символов.

Заключение

Алгоритмы поиска подстроки образуют базовый инструментарий обработки строк: от гарантированно линейных КМП/Z до практически очень быстрых Бойера–Мура и гибкого Рабина–Карпа. Понимание инвариантов (префиксы/суффиксы), грамотная предобработка и осознанный выбор алгоритма по характеристикам данных позволяют решать задачи строго и эффективно.

Для ЕГЭ по информатике темы поиска подстроки развивают навыки построения и доказательства линейных алгоритмов, анализа асимптотики, аккуратной работы с массивами и строками – компетенции, напрямую конвертируемые в высокие баллы.