Алгоритм поиска строки Бойера–Мура

Задача поиска подстроки (образца) в строке (тексте) – центральная в обработке текста, биоинформатике, информационном поиске и компиляторах. Алгоритм Бойера–Мура (BM) – классический эталон эффективного сопоставления строк, который достигает высокой производительности за счёт сравнения справа налево и применения эвристик сдвига. Его ключевая идея: при несовпадении символов не продвигаться по тексту на один шаг, как в наивном методе, а перепрыгивать большие участки благодаря знанию структуры образца.

Для подготовки к ЕГЭ по информатике BM полезен тем, что:

• развивает понимание строковых структур (суффиксы, границы, приставки),

• тренирует алгоритмическое мышление (инварианты, анализ худшего/среднего случая),

• укрепляет навык работы с таблицами предобработки и аккуратностью индексов,

• позволяет уверенно решать задания на поиск подстроки и оценку сложности.

Формальная постановка и базовая схема

Ключевые элементы BM:

1. сравнение символов выполняется с конца образца (начиная с позиции j=m−1);

2. при первом несовпадении на позиции j применяется максимальный допустимый сдвиг Δ≥1, вычисленный как максимум из двух эвристик:
   

• плохой символ (bad character, BC),

• хороший суффикс (good suffix, GS).

Эвристика плохого символа (Bad Character, BC)

Предобработка (массив last):
Для каждого символа алфавита σ запоминаем индекс последнего его вхождения в P (или −1, если отсутствует). Тогда сдвиг: 

Эвристика хорошего суффикса (Good Suffix, GS)

Как строить L и l (схематично):

1. Вычислить массив suf: для каждого i – длину наибольшего суффикса P[0..i], совпадающего с суффиксом всей строки P.

2. На основании suf заполнить l: для всех i, где наблюдается совпадение «хвоста с префиксом».

3. Заполнить L: пробежаться по позициям, отмечая, где встречается подстрока P[i+1..m−1] внутри P с требуемым отличием соседних символов.

Сложность предобработки: O(m).
Практическое замечание: корректная реализация GS – источник ошибок; важно аккуратное обращение с индексами.

Итоговый сдвиг и структура алгоритма

Правило сдвига: при несовпадении на позиции j сдвиг Δ=max (ΔBC, ΔGS). Это гарантирует, что не пропустим потенциальные вхождения и одновременно сделаем максимально безопасный шаг.

Псевдокод (схематично):

preprocess_BC(P)  -> last[σ]

preprocess_GS(P)  -> L[0..m-1], l[0..m-1]

s := 0

while s <= n - m:

    j := m - 1

    while j >= 0 and P[j] == T[s+j]:

        j := j - 1

    if j < 0:

        report match at s

        s := s + (m - l[0])                // сдвиг после полного совпадения

    else:

        bc := max(1, j - last[T[s+j]])     // плохой символ

        if L[j] > 0: gs := m - 1 - L[j]    // хороший суффикс

        else:         gs := m - l[j]

        s := s + max(bc, gs)

Инварианты корректности:

• при каждом сдвиге потенциальные совпадения не теряются (доказуемо из определения таблиц);

• сравнения всегда идут справа налево в пределах текущего выравнивания;

• выход за пределы текста не допускается (условие цикла по s).

Сложностной анализ

• Предобработка: O(m+Σ) по времени и O(m+Σ) по памяти (таблицы BC и GS).

• Поиск:
  

  • на практике близко к линейному времени O(n) за счёт крупных сдвигов;

  • худший случай для базового BM может достигать O(n⋅m) (искусственные тексты/шаблоны с большим числом частичных совпадений);

  • инженерные улучшения (например, правило Галиля, детальная реализация сильного GS) снижают избыточные сравнения и приближают поведение к линейному.

Связь с ЕГЭ: важно уметь объяснить разницу между средним и худшим случаями, корректно аргументировать асимптотику и понимать, что быстрое поведение BM обеспечивается структурой эвристик.

Практические правила корректной реализации

1. Единое соглашение об индексах (0-based) и чёткая трактовка «правого конца» (позиция m−1).

2. Инициализация last: для всех символов −1, затем один проход слева направо по P.

3. GS-таблицы: сначала вычислить массив суффиксов/границ, затем аккуратно заполнить l и L; проверять крайние случаи (повторяющиеся символы, «зубчатые» паттерны, полностью одинаковые символы).

4. Обработка полного совпадения: сдвиг на m−l[0], а не на 1 (иначе теряется смысл префиксной границы).

5. Юникод/многоалфавитность: для больших алфавитов удобно хранить last в хэш-отображении; для ASCII/кириллицы – компактный массив.

6. Фильтрация регистра/нормализация: если требуется регистронезависимый поиск, нормализовать и текст, и образец до предобработки.

7. Тесты граничных случаев: m=1, повторяющиеся символы (например, «A…»), отсутствующий символ, текст короче образца, совпадения в начале/в конце.

Связь с подготовкой к ЕГЭ

• Строки и алгоритмы: BM тренирует уверенную работу с индексами и циклами, что критично в задачах на строки.

• Доказательства и инварианты: понимание корректности сдвигов укрепляет умение обосновывать решения.

• Сложность: умение различать и аргументировать среднюю и худшую сложности.

• Табличные предобработки: системность в построении вспомогательных массивов – навык, часто встречающийся в олимпиадных/экзаменационных задачах.

Типичные ошибки и их профилактика

• Путаница индексов (j, s+j) при сравнении справа налево.

• Неверное заполнение last (оставленные по умолчанию «мусорные» значения).

• Ошибки в L, l из-за неправильных границ сравнения суффиксов/префиксов.

• Сдвиг 1 после совпадения всего образца – теряется преимущество GS.

• Игнорирование многоразовых совпадений (накладывающихся): нужно корректно сдвигать и продолжать поиск.

Пять упражнений (академический формат)

Упражнение 1. Ручная предобработка (BC).
Дан образец P = «EXAMPLE».
а) Постройте таблицу last для алфавита латинских заглавных (необязательные символы приравнять к −1).
б) Для каждого символа E, X, A, M, P, L укажите индекс последнего вхождения.
в) Объясните, какой сдвиг даст BC при несовпадении на правом конце, если в тексте стоит символ E.

Упражнение 2. Ручная предобработка (GS).

Упражнение 3. Полный проход по тексту.

Упражнение 4. Сложностной анализ (качественный).

Упражнение 5. Проверка корректности реализации.
 

Заключение

Алгоритм Бойера–Мура – образцовый пример того, как структура образца и правильная предобработка позволяют радикально ускорить поиск подстроки. Две эвристики – плохого символа и хорошего суффикса – обеспечивают крупные сдвиги и близкое к линейному время на практике. Для подготовки к ЕГЭ этот алгоритм ценен как тренажёр аккуратной индексной арифметики, строгих инвариантов и осмысленного анализа сложности. Отработав построение таблиц и отладив сдвиги на граничных случаях, вы получаете надёжный инструмент и уверенность при решении задач на строки.