Алгоритм Бойера–Мура: поиск подстроки с конца образца

Алгоритм Бойера–Мура и его упрощение Хорспула: эвристики плохого символа и хорошего суффикса, разбор на примере, сложность, код на Python и сравнение с KMP и Рабином–Карпом.

15 мин чтенияалгоритмы · строки · поиск подстрок · python

Коротко

ПараметрБойер–МурХорспул
ПредобработкаO(m+σ)O(m + \sigma)O(m+σ)O(m + \sigma)
Лучший случайO(n/m)O(n / m) сравненийO(n/m)O(n / m)
Худший случайO(n⋅m)O(n \cdot m), с правилом Галиля O(n+m)O(n + m)O(n⋅m)O(n \cdot m)
Памятьтаблица символов + массив на m+1m+1только таблица символов
Когда хорошдлинный образец, большой алфавит, обычный текстто же, но код в 15 строк

Где nn — длина текста, mm — длина образца, σ\sigma — размер алфавита.

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

Почему справа налево

Наивный поиск прикладывает образец к каждой позиции текста и сравнивает символы слева направо. KMP делает то же, но не откатывается назад по тексту: каждый символ текста он прочитает хотя бы один раз. Быстрее nn сравнений KMP работать не может.

Роберт Бойер и Джей Мур в 1977 году заметили, что, если сравнивать с конца образца, одно несовпадение может рассказать очень много. Ищем EXAMPLE (7 символов) и смотрим, что в тексте стоит напротив последней буквы образца. Там S. В слове EXAMPLE буквы S нет вообще, значит ни одно вхождение не может накрывать эту позицию. Образец можно сразу сдвинуть на 7 позиций, а 6 символов текста слева даже не читать.

Так получается главное свойство алгоритма: чем длиннее образец, тем длиннее прыжки и тем меньше символов текста приходится смотреть. KMP и Рабин–Карп такого не умеют.

Остаётся понять, на сколько сдвигать в общем случае. Для этого есть два правила.

Эвристика плохого символа

Пусть образец стоит со сдвигом s, мы сравниваем справа налево и на позиции j образца встретили несовпадение: pat[j] != text[s + j]. Символ c = text[s + j] называется плохим.

Сдвинем образец так, чтобы под c оказалось его последнее вхождение в образце, левее которого искать уже бессмысленно:

  • если c в образце нет, сдвигаем образец целиком за c: на j + 1;
  • если последнее вхождение c стоит на позиции last[c] < j, сдвиг равен j - last[c];
  • если last[c] > j (последнее вхождение правее места несовпадения), формула даёт ноль или отрицательное число. Тогда сдвигаем хотя бы на 1.

Если считать last[c] = -1 для отсутствующих символов, все три случая сводятся к одной формуле:

shift=max⁡(1,  j−last[c])\text{shift} = \max(1,\; j - \text{last}[c])

Таблица last строится одним проходом по образцу:

def build_last(pat): # последнее вхождение каждого символа в образце last = {} for i, ch in enumerate(pat): last[ch] = i return last def search_bad_char(text, pat): n, m = len(text), len(pat) if m == 0: return list(range(n + 1)) last = build_last(pat) res = [] s = 0 # сдвиг образца относительно текста while s <= n - m: j = m - 1 while j >= 0 and pat[j] == text[s + j]: j -= 1 if j < 0: res.append(s) s += 1 else: s += max(1, j - last.get(text[s + j], -1)) return res print(search_bad_char("HERE IS A SIMPLE EXAMPLE", "EXAMPLE")) # [17]

Словарь вместо массива на 256 или 65 536 элементов удобен в Python и для Unicode. В C или Java обычно берут массив размера алфавита: это и есть O(σ)O(\sigma) в оценке предобработки.

Одного правила плохого символа уже достаточно для быстрого поиска по обычному тексту. Слабое место видно на маленьком алфавите. Текст aaaa…a, образец baaa: совпадают три a, спотыкаемся на b, плохой символ a, его последнее вхождение last['a'] = 3 правее j = 0. Сдвиг — 1, и так на каждой позиции, по mm сравнений каждый раз. Это O(n⋅m)O(n \cdot m).

Эвристика хорошего суффикса

Второе правило использует то, что мы уже совпало. Если на позиции j случилось несовпадение, то суффикс образца t = pat[j+1:] совпал с текстом. Это «хороший суффикс». Куда можно сдвинуть образец, чтобы не потерять вхождение?

Случай 1. Строка t встречается в образце ещё раз, левее, и перед этим вхождением стоит символ, не равный pat[j]. Сдвигаем образец так, чтобы это вхождение (самое правое из подходящих) встало под совпавший кусок текста.

Условие про другой символ называют сильным правилом хорошего суффикса. Если перед повтором стоит тот же pat[j], после сдвига мы гарантированно снова споткнёмся на том же месте, поэтому такие повторы пропускаются.

Случай 2. Подходящего повтора нет. Тогда ищем самый длинный префикс образца, который совпадает с концом t. Его можно приложить к хвосту совпавшего куска. Если и такого нет, образец сдвигается целиком, на mm.

Пример на образце ABCAB:

Совпало (хороший суффикс)Несовпадение на jЧто нашлиСдвиг
ничего4правило ничего не даёт1
B3B есть на позиции 1, но перед ним A, как и pat[3] — не годится. Префикс, равный концу B, тоже не находится5
AB2повтора с другим символом нет, но префикс AB совпадает с суффиксом3
CAB, BCAB1, 0префикс AB всё ещё конец совпавшего куска3
весь образец—нашли вхождение, следующее начнётся не раньше чем через период ABCAB3

Вторая строка таблицы показывает пользу сильного правила. Слабое правило сдвинуло бы образец на 3, чтобы B на позиции 1 встал под совпавший B. Но тогда под A из текста окажется A из образца, а мы только что видели, что в тексте там не A. Проверка на позиции +3 заведомо провалится.

Как посчитать таблицу за O(m)

Наивно таблицу можно построить за O(m2)O(m^2) и даже O(m3)O(m^3), перебирая суффиксы и их вхождения. Классическая линейная версия похожа на построение префикс-функции, только для перевёрнутой строки: массив border[i] хранит начало самой длинной «границы» суффикса pat[i:], то есть его собственного суффикса, который одновременно является префиксом.

def build_good_suffix(pat): m = len(pat) shift = [0] * (m + 1) border = [0] * (m + 1) # случай 1: суффикс встречается в образце ещё раз i, j = m, m + 1 border[i] = j while i > 0: while j <= m and pat[i - 1] != pat[j - 1]: if shift[j] == 0: shift[j] = j - i j = border[j] i -= 1 j -= 1 border[i] = j # случай 2: только часть суффикса совпадает с префиксом образца j = border[0] for i in range(m + 1): if shift[i] == 0: shift[i] = j if i == j: j = border[j] return shift print(build_good_suffix("ABCAB")) # [3, 3, 3, 3, 5, 1]

Индексация такая: при несовпадении на позиции j берём shift[j + 1], а при полном совпадении — shift[0]. Первый цикл заполняет случай 1: когда pat[i-1] != pat[j-1], суффикс pat[j:] встречается начиная с i, а перед ним стоят разные символы — ровно сильное правило. Второй цикл дозаполняет оставшиеся ячейки случаем 2.

Этот код проще всего не выводить заново на собеседовании, а понимать, что он считает. Если надо написать с нуля, честнее сказать про наивный вариант за O(m2)O(m^2) и что существует линейный.

Полный алгоритм

Собираем оба правила. На каждом несовпадении считаем два сдвига и берём больший: каждое правило по отдельности гарантирует, что мы ничего не пропустили, значит пропустить нечего и при большем из них.

def boyer_moore(text, pat): n, m = len(text), len(pat) if m == 0: return list(range(n + 1)) last = build_last(pat) gs = build_good_suffix(pat) res = [] s = 0 while s <= n - m: j = m - 1 while j >= 0 and pat[j] == text[s + j]: j -= 1 if j < 0: res.append(s) s += gs[0] else: bc = j - last.get(text[s + j], -1) s += max(bc, gs[j + 1]) return res print(boyer_moore("HERE IS A SIMPLE EXAMPLE", "EXAMPLE")) # [17] print(boyer_moore("ABAAABCABCAB", "ABCAB")) # [4, 7] print(boyer_moore("aaaaa", "aa")) # [0, 1, 2, 3]

Все три функции из статьи я прогнал на 30 000 случайных строк над алфавитами из 1–4 букв и сверил с наивным поиском. Пересекающиеся вхождения находятся: после совпадения сдвиг gs[0] равен периоду образца, а не его длине.

Разбор на примере

Текст HERE IS A SIMPLE EXAMPLE (24 символа), образец EXAMPLE. Таблица last: E→6, X→1, A→2, M→3, P→4, L→5.

Сдвиг sОкно текстаГде споткнулисьПлохой символСдвиг по символуСдвиг по суффиксу
0HERE ISj=6, E против SS нет в образце71
7 A SIMPj=6, E против Plast[P]=421
9 SIMPLEj=2, A против II нет в образце36
15E EXAMPj=6, E против Plast[P]=421
17EXAMPLEсовпадение———

На шаге s=9 совпал хвост MPLE. Больше в образце он не встречается, но его последняя буква E — это префикс образца. Хороший суффикс сдвигает на 6, чтобы первая E встала под совпавшую E. Плохой символ дал бы только 3.

Итого 15 сравнений символов, причём 11 из 24 символов текста алгоритм не прочитал ни разу.

Алгоритм Хорспула

В 1980 году Найджел Хорспул предложил выбросить хороший суффикс и чуть изменить правило плохого символа. Сдвиг выбирается не по символу, на котором споткнулись, а всегда по символу текста под последней позицией окна, text[s + m - 1]. Сдвиг — расстояние от последнего вхождения этого символа в pat[0..m-2] до конца образца. Последний символ образца в таблицу не входит, иначе после совпадения последней буквы сдвиг был бы нулевым.

def horspool(text, pat): n, m = len(text), len(pat) if m == 0: return list(range(n + 1)) # сдвиг по символу, стоящему под ПОСЛЕДНЕЙ позицией окна shift = {} for i in range(m - 1): shift[pat[i]] = m - 1 - i res = [] s = 0 while s <= n - m: j = m - 1 while j >= 0 and pat[j] == text[s + j]: j -= 1 if j < 0: res.append(s) s += shift.get(text[s + m - 1], m) return res print(horspool("HERE IS A SIMPLE EXAMPLE", "EXAMPLE")) # [17] print(horspool("abababab", "abab")) # [0, 2, 4]

Сдвиг не зависит от того, где случилось несовпадение, поэтому таблица одна, отрицательных сдвигов не бывает, а внутренний цикл можно сравнивать хоть слева направо, хоть через memcmp. На тексте с большим алфавитом Хорспул почти не уступает полному Бойеру–Муру, а пишется за пару минут. Поэтому на практике чаще встречается именно он или его вариации (Sunday, Raita).

Сколько сравнений на самом деле

Я посчитал среднее число сравнений символов на один символ текста для четырёх алгоритмов. Тексты по миллиону символов: «английский» из случайных слов, случайная ДНК (алфавит ACGT) и два вырожденных случая.

Текст и образецНаивныйKMPБойер–МурХорспул
слова, образец algorithm (m=9m=9)1.131.040.230.23
слова, образец из 20 символов1.011.010.090.09
ДНК, m=12m=121.331.250.380.43
aaa…a, образец aaaaaaaaab10.02.01.01.0
aaa…a, образец baaaaaaaaa1.01.01.010.0

Что видно из таблицы:

  • На обычном тексте Бойер–Мур и Хорспул читают в 4–10 раз меньше символов, чем KMP. И чем длиннее образец, тем больше разрыв.
  • На маленьком алфавите (ДНК) выигрыш скромнее: почти любой символ встречается в образце недалеко от конца, сдвиги короткие. Здесь хороший суффикс уже заметно помогает.
  • Последняя строка — случай, где Хорспул деградирует до O(n⋅m)O(n \cdot m), а полный Бойер–Мур спасается хорошим суффиксом: совпавший хвост aaaaaaaaa больше нигде с другим символом впереди не встречается, и образец прыгает на всю длину.

Сложность

Предобработка. Таблица last — O(m+σ)O(m + \sigma), таблица хорошего суффикса — O(m)O(m).

Лучший случай — O(n/m)O(n / m): каждый раз первым же сравнением находим символ, которого нет в образце, и прыгаем на mm. Это сублинейное время, и в этом главное отличие от KMP, Z-функции и Рабина–Карпа.

Худший случай. В варианте выше, с поиском всех вхождений, худший случай — O(n⋅m)O(n \cdot m): текст aaaa…a и образец aaa…a. Совпадение на каждой позиции, каждое стоит mm сравнений, сдвиг — на период 1. Ричард Коул в 1991 году доказал, что при поиске первого вхождения с сильным правилом хорошего суффикса алгоритм делает не больше примерно 3n3n сравнений. Для поиска всех вхождений есть правило Галиля (1979): после совпадения запоминаем, какая часть окна заведомо совпадает с образцом, и не сравниваем её повторно. С ним худший случай — O(n+m)O(n + m).

Хорспул в худшем случае — O(n⋅m)O(n \cdot m), без вариантов. В среднем на случайном тексте он, как и Бойер–Мур, близок к O(n/m)O(n / m), пока mm заметно меньше размера алфавита.

Бойер–Мур, KMP или Рабин–Карп

KMPРабин–КарпБойер–Мур / ХорспулZ-функция
Худший случайO(n+m)O(n + m)O(n⋅m)O(n \cdot m), ожидаемо O(n+m)O(n + m)O(n⋅m)O(n \cdot m) без ГалиляO(n+m)O(n + m)
Типичный текст≈n\approx n сравненийnn пересчётов хеша≈n/m\approx n / m сравнений≈n\approx n
Читает текст потокомда, назад не возвращаетсяданет, нужно окнонет, склейка pat + # + text
Много образцовпо одномухорошо, хеши в множествоплохо (для этого есть Commentz-Walter)по одному
Сложность кодасредняянизкаявысокая (Хорспул — низкая)низкая

Как выбирать:

  • Один длинный образец, большой алфавит, текст целиком в памяти — Бойер–Мур или Хорспул. Так устроен поиск в текстовых редакторах и утилитах вроде grep, который для фиксированных строк использует алгоритмы семейства Бойера–Мура.
  • Поток символов, жёсткая гарантия O(n)O(n), маленький алфавит — KMP. Он читает каждый символ один раз и не требует буфера.
  • Много образцов одной длины или поиск повторяющихся подстрок — Рабин–Карп. Для словаря образцов разной длины — Ахо–Корасик.
  • Задачи на структуру строки (периоды, бордеры, палиндромы) — префикс- и Z-функция, а не Бойер–Мур.

Стандартные библиотеки тоже часто выбирают гибриды. Например, str.find в CPython — это упрощённый Бойер–Мур–Хорспул с битовой маской вместо таблицы, а для длинных образцов начиная с Python 3.10 включается алгоритм Two-Way с линейной гарантией.

Типичные ошибки

  1. Отрицательный сдвиг. Формула j - last[c] отрицательна, когда последнее вхождение c правее места несовпадения. Без max(1, ...) или без хорошего суффикса цикл уходит назад или зависает.
  2. Последний символ в таблице Хорспула. Если включить pat[m-1] в таблицу, его сдвиг будет 0 и поиск зациклится на первом же совпадении последней буквы.
  3. Сдвиг на mm после совпадения. Так теряются пересекающиеся вхождения: aa в aaaaa найдётся дважды вместо четырёх раз. Правильно — сдвиг на период образца (gs[0]) или на 1.
  4. Перепутанная индексация хорошего суффикса. В коде выше при несовпадении на j нужен shift[j + 1]. Ошибка на единицу ломает поиск только на части входов, поэтому проверяйте реализацию против наивного поиска на случайных строках из 2–3 букв: маленький алфавит быстро находит такие баги.
  5. Массив на 256 элементов для Unicode. В Python и Java символы не байты. Либо словарь, либо работа с байтами UTF-8.
  6. Путаница с majority vote. Если на собеседовании спросили «Бойер–Мур» в контексте массива и элемента, встречающегося больше n/2n/2 раз, речь об алгоритме голосования.

Что спрашивают на собеседованиях

Отдельной задачи «напишите Бойера–Мура» на LeetCode нет. Тема всплывает вокруг Find the Index of the First Occurrence in a String (LeetCode 28, бывший strStr): после наивного решения интервьюер может спросить, как сделать быстрее.

Хороший ответ выглядит так:

  1. Наивный поиск — O(n⋅m)O(n \cdot m), в большинстве реальных случаев этого хватает. String.indexOf в Java, например, по сути тот же перебор, только с аппаратными оптимизациями.
  2. Гарантированно линейно — KMP или Z-функция, O(n+m)O(n + m).
  3. На практике быстрее всего на обычном тексте — Бойер–Мур или Хорспул: сравниваем с конца, прыгаем по таблице плохого символа, в среднем читаем около n/mn / m символов.
  4. Если есть время, написать Хорспула. Он укладывается в 15 строк и легко объясняется на примере.

Полную таблицу хорошего суффикса на интервью почти никогда не требуют. Достаточно объяснить идею и показать на примере, почему она спасает от случая aaa…a / baaa…a. Если хочется закрепить строки шире, посмотрите подборку задач на строки и разбор нотации Big O, чтобы уверенно говорить про сублинейное время.

Потренироваться в спокойной обстановке

Все задачи