Просмотр кода страницы Алгоритм Бойера — Мура

{{эта статья|об алгоритме поиска подстроки|Алгоритм большинства голосов Бойера — Мура|об алгоритме поиска преобладающего элемента последовательности}}
{{Алгоритм
|предназначение=[[Поиск подстроки|Эффективный поиск подстроки в строке]]
|изображение=
|подпись=
|данные=[[Строковый тип|Строки]]
|время=<math>\Theta (n + m)</math>
|память=<math>\Theta(m + |\Sigma|)</math> или <math>\Theta(m)</math>
}}
'''Алгоритм поиска строки Бойера — Мура''' — алгоритм общего назначения, предназначенный для [[поиск подстроки|поиска подстроки в строке]]. Разработан {{нп3|Бойер, Стефан Роберт|Робертом Бойером|en|Robert S. Boyer}} и {{нп3|Мур, Джей|Джеем Муром|en|J Strother Moore}} в [[1977 год]]у{{sfn|Boyer, Moore|1977}}. Преимущество этого алгоритма <!-- по сравнению с каким алгоритмом? --> в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск), шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускается как заведомо не дающая результата.

Общая оценка [[Теория сложности вычислений|вычислительной сложности]] современного варианта алгоритма Бойера — Мура — <math>O(n + m)</math>, если не используется таблица стоп-символов (смотрите ниже), и <math>O(n + m + |\Sigma|)</math>, если используется таблица стоп-символов, где <math>n</math> — длина строки, в которой выполняется поиск, <math>m</math> — длина шаблона поиска, <math>\Sigma</math> — алфавит, на котором проводится сравнение{{sfn|Crochemore, Rytter|2002}}.

== Описание алгоритма ==
Алгоритм основан на трёх идеях.

'''1. Сканирование слева направо, сравнение справа налево.''' Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона. Если символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и выполняется поиск следующего вхождения подстроки.

Если же какой-то символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на ''несколько'' символов вправо, и проверка снова начинается с последнего символа.

Эти «несколько», упомянутые в предыдущем абзаце, вычисляются по двум эвристикам.

'''2. Эвристика стоп-символа.''' (''Замечание:'' эвристика стоп-символа присутствует в большинстве описаний алгоритма Бойера — Мура, включая оригинальную статью Бойера и Мура{{sfn|Boyer, Moore|1977}}, но не является необходимой для достижения оценки <math>O(n + m)</math> времени работы{{sfn|Crochemore, Rytter|2002}}; более того, данная эвристика для своей работы требует <math>O(|\Sigma|)</math> дополнительной памяти и <math>O(|\Sigma|)</math> дополнительного времени на этапе подготовки шаблона.)

Предположим, что мы производим поиск слова «колокол». Первая же буква не совпала — «к» (назовём эту букву ''стоп-символом''). Тогда можно сдвинуть шаблон вправо до ''последней'' его буквы «к».
                              
 Строка:          * * * * * * '''к''' * * * * * *
 Шаблон:          к о л о к о л
 Следующий шаг:       к о л о к о л

Если стоп-символа в шаблоне нет, шаблон смещается за этот стоп-символ.
                            
 Строка:          * * * * * '''а''' л * * * * * * * *
 Шаблон:          к о л о к о л
 Следующий шаг:               к о л о к о л

В данном случае стоп-символ — «а», и шаблон сдвигается так, чтобы он оказался прямо за этой буквой. В алгоритме Бойера — Мура эвристика стоп-символа вообще не смотрит на совпавший суффикс (см. ниже), так что первая буква шаблона («к») окажется под «л», и будет проведена одна заведомо холостая проверка.

Если стоп-символ «к» оказался за другой буквой «к», эвристика стоп-символа не работает.
                         
 Строка:         * * * * '''к''' к о л * * * * *
 Шаблон:           к о л о к о л
 Следующий шаг:  к о л о к о л    

В таких ситуациях выручает третья идея алгоритма Бойера — Мура — эвристика совпавшего суффикса.

'''3. Эвристика совпавшего суффикса.''' Неформально, если при чтении шаблона справа налево совпал суффикс S, а символ b, стоящий перед S в шаблоне (то есть шаблон имеет вид PbS), не совпал, то эвристика совпавшего суффикса сдвигает шаблон на наименьшее число позиций вправо так, чтобы строка S совпала с шаблоном, а символ, предшествующий в шаблоне данному совпадению S, отличался бы от b (если такой символ вообще есть). Формально, для данного шаблона <math>s[0..m{-}1]</math> считается целочисленный массив suffshift[0..m], в котором suffshift[i] равно минимальному числу <math>j > 0</math>, такому что <math>s[i{-}j] \ne s[i{-}1]</math> (если <math>i > 0</math> и <math>i - j \ge 0</math>) и <math>s[i{-}j{+}k] = s[i{-}1{+}k]</math> для любого <math>k > 0</math>, для которого выполняется <math>0 \le i - j + k < m</math> и <math>0 \le i - 1 + k < m</math> (для пояснения смотрите примеры ниже). Затем, если при чтении шаблона <math>s</math> справа налево совпало <math>k{-}1</math> символов <math>s[m{-}1], s[m{-}2], \ldots, s[m{-}k{+}1]</math>, а символ <math>s[m{-}k]</math> не совпал, то шаблон сдвигается на suffshift[m-k] символов вправо. Например:

 Строка:          * * * * * * р к а * * * * *
 Шаблон:          с к а л к а л к а
 Следующий шаг:               с к а л к а л к а

В данном случае совпал суффикс «ка», и шаблон сдвигается вправо до ближайшего «ка», перед которым нет буквы «л».

 Строка:          * * т о к о л * * * * *
 Шаблон:          к о л о к о л
 Следующий шаг:           к о л о к о л

В данном случае совпал суффикс «окол», и шаблон сдвигается вправо до ближайшего «окол», перед которым нет буквы «л». Если подстроки «окол» в шаблоне больше нет, но он начинается на «кол», сдвигается до «кол», и т. д.

'''Внимание''': несовпадение буквы перед ближайшим вхождением совпавшего суффикса является необходимым условием. Если ограничиться только сдвигом до ближайшего вхождения совпавшего суффикса, то алгоритм может работать неприемлемо медленно. Например, при поиске шаблона <math>cabababa\ldots ba</math> длины <math>2n</math> в строке <math>aaa\ldots aababab\ldots ba</math>, содержащей <math>2n</math> символов «a», за которыми следует строка <math>baba\ldots ba</math> длины <math>2n</math>, алгоритм, использующий сдвиги без учёта несовпадения символа, выполняет <math>O(n^2)</math> операций даже при использовании эвристики стоп-символов. С другой стороны доказано{{sfn|Crochemore, Rytter|2002}}, что время работы алгоритма БМ, учитывающего несовпадение символов (то есть использующего массив suffshift, определённый выше), равно <math>O(n + m)</math> даже без использования эвристики стоп-символов (данное в книге [[:en:Maxime Crochemore|М. Крошмора]] и [[:en:Wojciech Rytter|В. Риттера]]{{sfn|Crochemore, Rytter|2002}} доказательство этого факта является модификацией доказательства Коула 1994 года{{sfn|Cole|1994}}, рассмотревшего только случай непериодических шаблонов).

Обе эвристики требуют предварительных вычислений — в зависимости от шаблона поиска заполняются две таблицы. Таблица стоп-символов по размеру соответствует алфавиту — <math>O(|\Sigma|)</math> (например, если алфавит состоит из 256 символов, то её длина 256); таблица суффиксов — искомому шаблону, то есть <math>O(m)</math>.

Опишем подробнее обе таблицы.

=== Таблица стоп-символов ===
В таблице стоп-символов указывается последняя позиция в шаблоне <math>s</math> ('''исключая последнюю букву''') каждого из символов алфавита. Для всех символов, не вошедших в <math>s</math>, пишем 0, если нумерация символов начинается с 1 (или −1, если нумерация начинается с 0). Например, если <math>s=abcdadcd</math>, таблица стоп-символов StopTable будет выглядеть так (таблица приведена для случая строки, нумеруемой с нуля; при нумерации символов с единицы нужно прибавить ко всем числам единицу):

 Символ              a  b  c  d  [все остальные]
 Последняя позиция   4  1  6  5  -1

Обратите внимание, для стоп-символа «d» последняя позиция будет 5, а не 7 — последняя буква не учитывается. Это известная ошибка, приводящая к неоптимальности. Для алгоритма БМ она не фатальна (спасает положение эвристика суффикса), но фатальна для упрощённой версии алгоритма БМ — [[алгоритм Бойера-Мура-Хорспула|алгоритма Хорспула]].

Если при сравнении справа налево шаблона <math>s[0..m{-}1]</math> со строкой <math>text[i..i{+}m{-}1]</math> несовпадение произошло в позиции <math>j</math>, а стоп-символ — <math>c = text[j]</math>, то шаблон необходимо сдвинуть на <math>i' = j-StopTable[c]</math> символов.

=== Таблица суффиксов ===
Для каждого возможного суффикса <math>t</math> данного шаблона <math>s</math> указываем наименьшую величину, на которую нужно сдвинуть вправо шаблон, чтобы он снова совпал с <math>t</math> и при этом символ, предшествующий этому вхождению <math>t</math>, не совпадал бы с символом, предшествующим суффиксу <math>t</math>. Если такой сдвиг невозможен, ставится <math>|s| = m</math> (в обеих системах нумерации). Например, для <math>s=aaccbccbcc</math> будет:

 Суффикс        [пустой]         c       cc        bcc            ...   aaccbccbcc
 Сдвиг               2           1        6         10            ...           10
 Иллюстрация
     было            ?          ?c      ?cc       ?bcc            ...   aaccbccbcc
     стало    aaccbccbcc aaccbccbcc    aaccbccbcc     aaccbccbcc  ...             aaccbccbcc

Для <math>s=</math>«колокол»:

 Суффикс      [пустой]        л         ол        кол       ...  олокол        колокол
 Сдвиг              1         7          7        4         ...       4              4
 Иллюстрация
     было           ?        ?л        ?ол        ?кол      ... ?олокол        колокол
     стало     колокол         колокол    колокол  колокол  ...     колокол        колокол

Существует алгоритм вычисления таблицы суффиксов suffshift[0..m] с временем работы <math>O(m)</math>.{{sfn|Crochemore, Rytter|2002}} Этот алгоритм основан на тех же идеях, что и алгоритмы вычисления [[префикс-функция|префикс-функции]] и [[Z-функция|Z-функции]] строки{{sfn|Гасфилд|2003}}<ref name="e-maxx">{{Cite web |url=http://e-maxx.ru/algo/z_function |title=MAXimal :: algo :: Z-функция строки и её вычисление<!-- Заголовок добавлен ботом --> |access-date=2017-03-14 |archive-date=2017-04-26 |archive-url=https://web.archive.org/web/20170426224256/http://e-maxx.ru/algo/z_function |deadlink=no }}</ref>. Реализация данного алгоритма на C++ выглядит следующим образом:

<source lang="cpp">
 std::vector<int> suffshift(m + 1, m);
 std::vector<int> z(m, 0);
 for (int j = 1, maxZidx = 0, maxZ = 0; j < m; ++j) {
   if (j <= maxZ) z[j] = std::min(maxZ - j + 1, z[j - maxZidx]);
   while (j + z[j] < m && s[m - 1 - z[j]] == s[m - 1 - (j + z[j])]) z[j]++;
   if (j + z[j] - 1 > maxZ) {
     maxZidx = j;
     maxZ = j + z[j] - 1;
   }
 }
 for (int j = m - 1; j > 0; j--) suffshift[m - z[j]] = j; //цикл №1
 for (int j = 1, r = 0; j <= m - 1; j++) //цикл №2
   if (j + z[j] == m)
     for (; r <= j; r++)
       if (suffshift[r] == m) suffshift[r] = j;
</source>

В первом цикле в коде воспроизведён код вычисления так называемой [[Z-функция|Z-функции]] <math>z[1..m{-}1]</math>, но для перевёрнутой строки <math>s[0..m-1]</math>.<ref name="e-maxx" /> А именно, для любого <math>j</math>, такого что <math>0 \le j < m-1</math>, элемент <math>z[m - 1 - j]</math> содержит длину длиннейшего суффикса строки <math>s[0..j]</math>, который также является суффиксом всей строки <math>s</math>. С помощью массива <math>z</math> далее вычисляется искомый массив suffshift[0..m] (смотрите описание ниже). На каждой итерации последнего цикла <math>j</math> уменьшается на 1, а на каждой итерации вложенного в него цикла <math>k</math> уменьшается на 1. Поэтому, так как <math>j \ge 0</math>, <math>k \ge 0</math>, и алгоритм вычисления Z-функции работает за <math>O(m)</math> (смотрите, например, соответствующую [[Z-функция|статью]], а также статью<ref name="e-maxx" />), общее время работы данного алгоритма — <math>O(m)</math>.

Для доказательства корректности представленного кода удобно представлять себе, что анализируется строка <math>s'[0..m{-}1]</math>, которая равна перевёрнутой строке <math>s</math>. По определению suffshift, имеем suffshift[<math>m - k</math>]<math> = j</math>, где <math>j</math> — это наименьшее положительное число, такое что либо 1) строка <math>s'[j..m{-}1]</math> является префиксом строки <math>s'[0..k{-}1]</math>, либо 2) строка <math>s'[j..j{+}k{-}1]</math> равна <math>s'[0..k{-}1]</math>, а символы <math>s'[j{+}k]</math> и <math>s'[k]</math> отличаются. В случае 2), по определению <math>z</math>, обязательно выполняется <math>z[j] = k</math>. Таким образом, пробегая по <math>j</math> от <math>m-1</math> до 1, цикл № 1 находит все значения suffshift, полученные по правилу 2). Для вычисления значений suffshift, полученных по правилу 1), заметим, что, во-первых, если <math>s'[j..m{-}1]</math> — префикс <math>s'[0..k{-}1]</math>, то обязательно выполняется <math>j + z[j] = m</math>, а во-вторых, если suffshift[<math>r</math>] = <math>j</math> для какого-то <math>r</math>, то обязательно <math>r \le j</math>. Опираясь на эти два наблюдения, цикл № 2 вычисляет оставшиеся неинициализированными значения suffshift (то есть такие что suffshift[k] = m).

=== Реализация алгоритма ===

Пусть массив сдвигов suffshift[0..m] для данного шаблона <math>s[0..m{-}1]</math> посчитан. Тогда реализация на C++ алгоритма Бойера — Мура для поиска первого вхождения <math>s</math> в тексте <math>text[0..n{-}1]</math> за <math>O(n + m)</math> времени без применения эвристики стоп-символов выглядит следующим образом{{sfn|Crochemore, Rytter|2002}}:

<source lang="cpp">
 for (int i = 0, j = 0; i <= n - m && j >= 0; i += suffshift[j+1]) {
   for (j = m - 1; j >= 0 && s[j] == text[i + j]; j--);
   if (j < 0) report_occurrence(i);
 }
</source>

Такой алгоритм непригоден для поиска всех вхождений шаблона в текст за <math>O(m + n)</math> времени. Если убрать условие «j >= 0» из внешнего цикла, то алгоритм найдёт все вхождения, но в худшем случае, возможно, выполнит <math>O(mn)</math> операций, в чём легко убедиться, рассмотрев строку, состоящую из одних букв «a». Для поиска всех вхождений используют следующую модификацию, которая работает <math>O(n + m)</math> времени за счёт так называемого правила Галиля{{sfn|Galil|1979}}:

<source lang="cpp">
 int j, bound = 0; //всегда либо bound = 0, либо bound = m - suffshift[0]
 for (int i = 0; i <= n - m; i += suffshift[j+1]) {
   for (j = m - 1; j >= bound && s[j] == text[i + j]; j--);
   if (j < bound) {
     report_occurrence(i);
     bound = m - suffshift[0];
     j = -1; //установить j так, как будто мы прочитали весь шаблон s, а не только до границы bound
   } else {
     bound = 0;
   }
 }
</source>

Правило Галиля основано на следующем несложном наблюдении. Если вхождение <math>s</math> найдено в позиции <math>i</math>, то следующий поиск будет пытаться найти вхождение шаблона в позиции <math>i' = i + </math>suffshift[0] и, по определению suffshift, уже известно, что символы <math>s[i'], s[i'{+}1], \ldots, s[i{+}m{-}1]</math> совпадают с символами <math>s[0], s[1], \ldots, s[m{-}</math>suffshift[0]<math>{-}1]</math>. Значит, при выполнении поиска справа налево для определения того, есть ли вхождение шаблона в позиции <math>i'</math>, нет смысла проверять символы <math>s[0], s[1], \ldots, s[m{-}</math>suffshift[0]<math>{-}1]</math>. Именно для этого и служит переменная «bound». Доказано, что такая эвристика помогает получить <math>O(n + m)</math> времени для поиска всех вхождений шаблона в строку{{sfn|Galil|1979}}.

Для включения эвристики стоп-символов достаточно строку «<code>i += suffshift[j+1]</code>» заменить на следующее выражение в конце основного цикла:
<source lang="cpp">
  if (j < bound) i += suffshift[j+1]; 
  else i += max(suffshift[j+1], j - StopTable[text[i + j]]);
</source>

== Пример работы алгоритма ==
Искомый шаблон — «<code>abbad</code>». Таблица стоп-символов будет выглядеть как (в данном примере будет удобнее пользоваться нумерацией с единицы)

 Символ   a  b  d  [остальные]
 Позиция  1  2  5  0

Таблица суффиксов для всех возможных суффиксов (кроме пустого) даёт максимальный сдвиг — 5.

 abeccaabadbabbad
 abbad

Накладываем образец на строку. Совпадения суффикса нет — таблица суффиксов даёт сдвиг на одну позицию. Для несовпавшего символа исходной строки «<code>с</code>» (5-я позиция) в таблице стоп-символов записан 0. Сдвигаем образец вправо на <code>5-0=5</code> позиций.

 abeccaabadbabbad
      abbad

Символы 3—5 совпали, а второй — нет. Эвристика для «<code>а</code>» не работает (<code>2-4=-2</code>). Но поскольку часть символов совпала, в дело включается эвристика совпавшего суффикса, сдвигающая шаблон сразу на пять позиций!

 abeccaabadbabbad
           abbad

И снова совпадения суффикса нет. В соответствии с таблицей стоп-символов сдвигаем образец на одну позицию и получаем искомое вхождение образца:

 abeccaabadbabbad
            abbad

== Доказательство корректности ==

Для доказательства корректности алгоритма достаточно показать, что если та или иная эвристика предлагает сдвиг более чем на одну позицию вправо, на пропущенных позициях шаблон не найдётся.

Итак, пусть совпал суффикс ''S'', строка-шаблон равна ''PbS'', стоп-символ — ''a'' (в дальнейшем малые буквы — символы, большие — строки).

 Строка:     * * * * * * * a [-- S --] * * * *
 Шаблон:       [--- P ---] b [-- S --]

'''Эвристика стоп-символа.''' Работает, когда в строке ''V'' символ ''а'' отсутствует. Если ''P=WaV'' и в строке ''V'' нет символа ''а'', то эвристика стоп-символа предлагает сдвиг на |''V''|+1 позицию.

 Строка:     * * * * * * * * * * * * a [-- S --] * * * * * * * *
 Шаблон:       [- W -] a [--- V ---] b [-- S --]
 Пропустить:             [- W -] a [--- V ---] b [-- S --]
 Новый шаг:                  [- W -] a [--- V ---] b [-- S --]

Действительно, если в строке ''V'' нет буквы ''a'', нечего пробовать пропущенные |''V''| позиций.

Если же в шаблоне нет символа ''а'', то эвристика стоп-символа предлагает сдвиг на |''P''|+1 позицию — и также нет смысла пробовать пропущенные |''P''|.

 Строка:     * * * * * * * * a [-- S --] * * * * * * * *
 Шаблон:         [--- P ---] b [-- S --]
 Пропустить:         [--- P ---] b [-- S --]
 Новый шаг:                    [--- P ---] b [-- S --]

'''Эвристика совпавшего суффикса.''' Сама неформальная фраза — «наименьшая величина, на которую нужно сдвинуть вправо шаблон, чтобы он снова совпал с S, но символ перед данным совпадением с S (если такой символ существует) отличался бы от b» — говорит, что меньшие сдвиги бесполезны.

== Варианты ==

=== Алгоритм Бойера — Мура — Хорспула ===
{{See also|Алгоритм Бойера — Мура — Хорспула}}
Алгоритм Бойера — Мура — Хорспула (АБМХ) работает лучше алгоритма Бойера — Мура (АБМ) на ''случайных'' текстах — для него [[оценка в среднем]] лучше.

АБМХ использует только эвристику стоп-символа; при этом за стоп-символ берётся символ входной строки, который соответствует последнему символу шаблона, '''независимо от того, где случилось несовпадение'''.

Поскольку реальные поисковые образцы редко имеют [[Дискретное равномерное распределение|равномерное распределение]], АБМХ может дать как выигрыш, так и проигрыш по сравнению с АБМ.

=== Алгоритм Чжу — Такаоки ===

На коротких алфавитах (например, при сравнении участков [[ДНК]] алфавит состоит всего из четырёх символов: [[аденин|A]], [[тимин|Т]], [[гуанин|Г]], [[цитозин|Ц]]) эвристика стоп-символа отказывает уже на коротких суффиксах. Простейший способ улучшить работу АБМ в таких условиях — вместо одного стоп-символа строить таблицу для пары символов: несовпавшего и идущего перед ним<ref>[http://www-igm.univ-mlv.fr/~lecroq/string/node20.html Zhu-Takaoka algorithm] {{Wayback|url=http://www-igm.univ-mlv.fr/~lecroq/string/node20.html |date=20081216070449 }}{{ref-en}}</ref>. Такой алгоритм был назван алгоритмом Чжу — Такаоки.

На предварительную обработку расходуется <math>O(m + |\Sigma|^2)</math> времени.

=== Алгоритм «турбо-Бойера — Мура» ===

Алгоритм «турбо-Бойера — Мура» разработан группой учёных во главе с [[Крошмор, Максим|М. Крошмором]], предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае.

Помимо эвристики стоп-символа и эвристики совпавшего суффикса, применяется третья эвристика — '''эвристика турбосдвига'''<ref>[http://www-igm.univ-mlv.fr/~lecroq/string/node15.html Turbo-BM algorithm] {{Wayback|url=http://www-igm.univ-mlv.fr/~lecroq/string/node15.html |date=20081216073030 }}{{ref-en}}</ref>.

Пусть первый раз совпал суффикс ''UV'' (и сработала эвристика суффиксов, обеспечив полное перекрытие этого суффикса), второй раз — более короткий ''V'' (возможно, ''V''=∅).

                                                !                     !
 входная строка:      * * * * * * * * * * # [-U-] [V] * * * * * * * * # [V] * * * * * *
 1. Совпало UV:         * [-U-] [V] * * * * [-U-] [V]
 2. Затем совпало V:                      * [-U-] [V] * * * * * * [-U-] [V]
 Сдвиг по эвристике суффиксов:                * [-U-] [V] * * * * * * [-U-] [V]
 Турбосдвиг:                                    * [-U-] [V] * * * * * * [-U-] [V]

По рисунку видно, что минимально возможный сдвиг — |''U''|. В противном случае два символа, обозначенные восклицательными знаками, во входной строке разные, а в шаблоне одинаковые. В этом и заключается эвристика турбосдвига.

Алгоритм выполняет свою работу за <math>2 n</math> сравнений до первого совпадения в худшем случае.

== Сравнение с другими алгоритмами ==

=== Достоинства ===

Алгоритм Бойера — Мура на «хороших» данных очень быстр{{Уточнить}}, а вероятность появления «плохих» данных крайне мала. Поэтому он оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста, в котором проводится поиск<ref>[http://www-igm.univ-mlv.fr/~lecroq/string/node2.html Exact string matching algorithms — Introduction] {{Wayback|url=http://www-igm.univ-mlv.fr/~lecroq/string/node2.html |date=20081216010527 }}{{ref-en}}</ref>. Разве что на коротких текстах выигрыш не оправдает предварительных вычислений.

=== Недостатки ===

Алгоритмы семейства Бойера — Мура не расширяются до приблизительного поиска, поиска любой строки из нескольких.

Сравнение не является «[[чёрный ящик|чёрным ящиком]]» (только если применяется эвристика стоп-символа), поэтому при реализации наиболее быстрого поиска приходится либо рассчитывать на удачную работу [[оптимизация компилятора|оптимизатора]], либо вручную оптимизировать поиск на языке ассемблера.

Если текст изменяется редко, а поиск проводится часто (например, [[поисковая машина|поисковой машиной]]), можно провести индексацию текста. Алгоритм поиска по индексу быстрее{{Уточнить}} алгоритма Бойера — Мура.

На больших алфавитах (например, [[Юникод]]) таблица стоп-символов может занимать много памяти. В таких случаях либо обходятся [[хеш-таблица]]ми, либо дробят алфавит, рассматривая, например, 4-байтовый символ как пару двухбайтовых, либо (что проще всего) пользуются вариантом алгоритма Бойера — Мура без эвристики стоп-символов.

Существует ряд модификаций алгоритма Бойера — Мура, нацеленных на ещё большее ускорение — например, турбо-алгоритм, обратный [[алгоритм Колусси]]<ref>[http://www-igm.univ-mlv.fr/~lecroq/string/node17.html Reverse Colussi algorithm] {{Wayback|url=http://www-igm.univ-mlv.fr/~lecroq/string/node17.html |date=20160309174327 }}{{ref-en}}</ref> и другие.

== См. также ==
* [[Алгоритм Кнута — Морриса — Пратта]]
* [[Алгоритм Рабина — Карпа]]
* [[Алгоритм Ахо — Корасик]]

== Примечания ==
{{примечания}}

== Литература ==
{{wikibooks|Реализации алгоритмов/Алгоритм Бойера — Мура|Алгоритм Бойера — Мура}}
* {{книга
  |автор=[[Кормен, Томас|Кормен Т. Х.]], [[Лейзерсон, Чарльз|Лейзерсон Ч. Е.]], [[Ривест, Рональд|Ривест Р. Л.]], [[Штайн, Клиффорд|Штайн К.]]
  |заглавие= [[Алгоритмы: построение и анализ]]
  |оригинал=Introduction to Algorithms
  |год=2005
  |страниц=801
  |место=М.
  |издательство= Вильямс
  |isbn=5-8459-0857-4
  |издание=2-е изд
  |ответственный=под ред. {{nobr|С. Н. Тригуба}}; пер. с англ. {{nobr|И. В. Красиков}}, {{nobr|Н. А. Орехов}}, {{nobr|В. Н. Романов}}
  |ref=Кормен, Лейзерсон, Ривест, Штайн
}}
* {{книга
  |автор=[[:en:Maxime Crochemore|Crochemore M.]], [[:en:Wojciech Rytter|Rytter W.]]
  |заглавие= Jewels of Stringology
  |издательство= World Publishing Scientific Co. Pte. Ltd.
  |место=Singapore
  |год=2002
  |страниц=310
  |isbn=981-02-4782-6
  |ref=Crochemore, Rytter
}}
* {{статья
  |автор=[[:en:Robert S. Boyer|Boyer R. S.]], [[:en:J Strother Moore|Moore J. S.]]
  |заглавие= A fast string searching algorithm
  |издание= [[Communications of the ACM]]
  |номер=10
  |том=20
  |страницы=762—772
  |год=1977
  |ref=Boyer, Moore
  |doi=10.1145/359842.359859
}}
* {{статья
  |автор=Cole R.
  |заглавие= Tight bounds on the complexity of the Boyer-Moore string matching algorithm
  |издание= [[:en:SIAM Journal on Computing|SIAM Journal on Computing]]
  |номер=5
  |том=23
  |страницы=1075—1091
  |год=1994
  |ref=Cole
  |doi=10.1137/S0097539791195543
}}
* {{статья
  |автор=[[:en:Zvi Galil|Galil Z.]]
  |заглавие= On improving the worst case running time of the Boyer-Moore string matching algorithm
  |издание= [[Communications of the ACM]]
  |номер=9
  |том=22
  |страницы=505—508
  |год=1979
  |ref=Galil
  |doi=10.1145/359146.359148
}}
* {{книга
  |автор=Гасфилд Д.
  |заглавие= Строки, деревья и последовательности в алгоритмах: информатика и вычислительная биология
  |оригинал=Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology
  |год=2003
  |страниц=654
  |место=СПб.
  |издательство= Невский Диалект
  |isbn=5-7940-0103-8
  |ответственный = пер. с англ. {{nobr|И. В. Романовский}}
  |ref=Гасфилд
}}
{{Строки}}
[[Категория:Поиск подстроки|Бойера — Мура]]
[[Категория:Эвристические алгоритмы]]