Алгоритм поиска строки Бойера – Мура - Boyer–Moore string-search algorithm

В Информатика, то Алгоритм поиска строки Бойера – Мура эффективный алгоритм поиска строки это стандартный ориентир для практической литературы по поиску строк.^[1] Он был разработан Роберт С. Бойер и Дж. Стротер Мур в 1977 г.^[2] Исходный документ содержал статические таблицы для вычисления сдвигов паттернов без объяснения того, как их производить. Алгоритм создания таблиц был опубликован в следующей статье; эта статья содержала ошибки, которые позже были исправлены Войцех Риттер в 1980 г.^[3][4] В алгоритм препроцессы то строка ищется (шаблон), но не строка, в которой ищется (текст). Таким образом, он хорошо подходит для приложений, в которых шаблон намного короче текста или где он сохраняется при нескольких поисках. Алгоритм Бойера – Мура использует информацию, собранную на этапе предварительной обработки, для пропуска частей текста, что приводит к более низкому постоянному коэффициенту, чем многие другие алгоритмы поиска по строкам. В общем, алгоритм работает быстрее по мере увеличения длины шаблона. Ключевые особенности алгоритма состоят в том, чтобы соответствовать хвосту шаблона, а не его заголовку, и пропускать текст скачками из нескольких символов, а не искать каждый отдельный символ в тексте.

Определения

• S[я] обозначает символ в индексе я строки S, считая от 1.
• S[я..j] обозначает подстрока строки S начиная с индекса я и заканчивая j, включительно.
• А приставка из S это подстрока S[1..я] для некоторых я в диапазоне [1, п], где п это длина S.
• А суффикс из S это подстрока S[я..п] для некоторых я в диапазоне [1, п], где п это длина S.
• Строка, которую нужно искать, называется шаблон и обозначается п. Его длина п.
• Строка, в которой выполняется поиск, называется текст и обозначается Т. Его длина м.
• An выравнивание из п к Т это индекс k в Т так что последний символ п выровнен с индексом k из Т.
• А матч или вхождение из п происходит при выравнивании, если п эквивалентно Т[(k-п+1)..k].

Описание

Алгоритм Бойера – Мура ищет вхождения п в Т путем выполнения явного сравнения символов при разных выравниваниях. Вместо перебор всех выравниваний (из них ${ displaystyle m-n + 1}$), Бойер-Мур использует информацию, полученную при предварительной обработке п чтобы пропустить как можно больше выравниваний.

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

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

Более формально алгоритм начинается с выравнивания ${ Displaystyle к = п}$, так что начало п совпадает с началом Т. Персонажи в п и Т затем сравниваются, начиная с индекса п в п и k в Т, двигаясь назад. Строки сопоставляются с конца п к началу п. Сравнение продолжается до начала п достигается (что означает совпадение) или возникает несоответствие, при котором выравнивание сдвигается вперед (вправо) в соответствии с максимальным значением, разрешенным рядом правил. Сравнение выполняется снова при новом выравнивании, и процесс повторяется до тех пор, пока выравнивание не смещается за конец Т, что означает, что больше совпадений найдено не будет.

Правила сдвига реализованы как поиск в таблице с постоянным временем с использованием таблиц, сгенерированных во время предварительной обработки п.

Правила смены

Сдвиг рассчитывается с применением двух правил: правила плохого символа и правила хорошего суффикса. Фактическое смещение смещения - это максимальное смещение, рассчитанное по этим правилам.

Правило плохого характера

Описание

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

Предварительная обработка

Методы различаются в зависимости от точной формы, которую должна принимать таблица для правила плохого символа, но простое решение для поиска с постоянным временем выглядит следующим образом: создать 2D-таблицу, которая сначала индексируется по индексу символа. c по алфавиту и секунд по индексу я в выкройке. Этот поиск вернет вхождение c в п со следующим по величине индексом ${ displaystyle j$ или -1, если такого случая нет. Предлагаемая смена тогда будет ${ displaystyle i-j}$, с участием ${ Displaystyle O (1)}$ время поиска и ${ Displaystyle О (кн)}$ пространство, предполагая конечный алфавит длины k.

Реализации C и Java ниже имеют ${ Displaystyle О (к)}$ сложность пространства (make_delta1, makeCharTable). Это то же самое, что и исходная delta1, а Таблица неверных символов BMH. Эта таблица отображает символ в позиции ${ displaystyle i}$ сдвинуть ${ displaystyle operatorname {len} (p) -1-i}$, причем последний экземпляр - наименьшее количество сдвига - имеет приоритет. Все неиспользуемые символы устанавливаются как ${ displaystyle operatorname {len} (p)}$ как контрольное значение.

Правило хорошего суффикса

Описание

Правило хорошего суффикса значительно сложнее как по концепции, так и по реализации, чем правило плохого символа. Как и правило плохого символа, оно также использует свойство алгоритма сравнения, начинающегося в конце шаблона и продолжающегося к началу шаблона. Его можно описать так:^[5]

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

Предварительная обработка

Правило хорошего суффикса требует двух таблиц: одну для использования в общем случае, а другую для использования, когда либо общий случай не возвращает значимого результата, либо происходит совпадение. Эти таблицы будут обозначены L и ЧАС соответственно. Их определения следующие:^[5]

Для каждого я, ${ Displaystyle L [я]}$ самая большая позиция меньше чем п такая строка ${ displaystyle P [i..n]}$ совпадает с суффиксом ${ Displaystyle P [1..L [я]]}$ и такой, что символ, предшествующий этому суффиксу, не равен ${ Displaystyle P [я-1]}$. ${ Displaystyle L [я]}$ считается равным нулю, если нет позиции, удовлетворяющей условию.

Позволять ${ Displaystyle Н [я]}$ обозначают длину наибольшего суффикса ${ displaystyle P [i..n]}$ это также префикс п, если таковой существует. Если его нет, пусть ${ Displaystyle Н [я]}$ быть нулевым.

Обе эти таблицы могут быть построены в ${ Displaystyle О (п)}$ время и использование ${ Displaystyle О (п)}$ Космос. Сдвиг выравнивания для индекса я в п дан кем-то ${ Displaystyle п-L [я]}$ или ${ Displaystyle н-Н [я]}$. ЧАС следует использовать только если ${ Displaystyle L [я]}$ равен нулю или найдено совпадение.

Правило Галиля

Простая, но важная оптимизация Бойера – Мура была предложена Галил в 1979 г.^[6]В отличие от сдвига, правило Галиля имеет дело с ускорением фактических сравнений, выполняемых при каждом выравнивании, путем пропуска разделов, которые, как известно, совпадают. Предположим, что при выравнивании k₁, п сравнивается с Т вплоть до характера c из Т. Тогда если п переносится на k₂ так что его левый конец находится между c и k₁, на следующем этапе сравнения префикс п должна соответствовать подстроке Т[(k₂ - п)..k₁]. Таким образом, если сравнения сводятся к позиции k₁ из Т, появление п можно записать без явного сравнения прошлых k₁. Помимо повышения эффективности Бойера – Мура, правило Галиля требуется для доказательства линейного выполнения в наихудшем случае.

Правило Galil в его исходной версии действует только для версий, которые выводят несколько совпадений. Он обновляет диапазон подстроки только на c = 0, т.е. полное совпадение. Обобщенная версия для работы с подматчами была представлена ​​в 1985 году как Алгоритм Апостолико – Джанкарло.^[7]

Спектакль

Алгоритм Бойера-Мура, представленный в исходной статье, имеет время работы в худшем случае ${ Displaystyle О (п + т)}$ только если шаблон не появляются в тексте. Впервые это было доказано Knuth, Моррис, и Пратт в 1977 г.^[8]с последующим Гибас и Одлызко в 1980 г.^[9] с верхней границей 5п сравнения в худшем случае. Ричард Коул дал доказательство с оценкой сверху 3п сравнения в худшем случае в 1991 году.^[10]

Когда узор делает встречаются в тексте, время работы исходного алгоритма равно ${ Displaystyle O (нм)}$ в худшем случае. Это легко увидеть, если и шаблон, и текст состоят исключительно из одного и того же повторяющегося символа. Однако включение Правило Галила приводит к линейному времени выполнения во всех случаях.^[6][10]

Реализации

Существуют разные реализации на разных языках программирования. В C ++ это часть стандартной библиотеки, начиная с C ++ 17, а также Увеличение предоставляет общий поиск Бойера – Мура реализация в рамках Алгоритм библиотека. В Go (язык программирования) есть реализация в search.go. D (язык программирования) использует BoyerMooreFinder для сопоставления на основе предикатов в пределах диапазонов как часть библиотеки времени выполнения Phobos.

Алгоритм Бойера – Мура также используется в GNU с grep.^[11]

Ниже приведены несколько простых реализаций.

от набор текста импорт *# Эта версия чувствительна к английскому алфавиту в ASCII для соответствия без учета регистра.# Чтобы удалить эту функцию, определите алфавитный_индекс как ord (c) и замените экземпляры "26"# с "256" или любой другой максимальной кодовой точкой, которую вы хотите. Для Unicode вы можете сопоставить UTF-8# байт вместо создания таблицы размером 0x10FFFF.ALPHABET_SIZE = 26def алфавит_индекс(c: ул) -> int:    "" "Возвращает индекс данного символа в английском алфавите, считая от 0." ""    вал = ord(c.ниже()) - ord("а")    утверждать вал >= 0 и вал < ALPHABET_SIZE    вернуть валdef match_length(S: ул, idx1: int, idx2: int) -> int:    "" "Возвращает длину совпадения подстрок S, начинающихся с idx1 и idx2." ""    если idx1 == idx2:        вернуть len(S) - idx1    match_count = 0    в то время как idx1 < len(S) и idx2 < len(S) и S[idx1] == S[idx2]:        match_count += 1        idx1 += 1        idx2 += 1    вернуть match_countdef фундаментальный_препроцесс(S: ул.) -> Список[int]:    "" "Return Z, фундаментальная предварительная обработка S.    Z [i] - длина подстроки, начинающейся с i, которая также является префиксом S.    Эта предварительная обработка выполняется за время O (n), где n - длина S.    """    если len(S) == 0:  # Обрабатывает регистр пустой строки        вернуть []    если len(S) == 1:  # Обрабатывает регистр односимвольной строки        вернуть [1]    z = [0 для Икс в S]    z[0] = len(S)    z[1] = match_length(S, 0, 1)    для я в ассортимент(2, 1 + z[1]):  # Оптимизация из упражнения 1-5        z[я] = z[1] - я + 1    # Определяет нижний и верхний пределы z-бокса    л = 0    р = 0    для я в ассортимент(2 + z[1], len(S)):        если я <= р:  # я попадает в существующий z-блок            k = я - л            б = z[k]            а = р - я + 1            если б < а:  # b заканчивается внутри существующего z-блока                z[я] = б            еще:  # b заканчивается в конце z-блока или после него, нам нужно сделать явное совпадение справа от z-блока                z[я] = а + match_length(S, а, р + 1)                л = я                р = я + z[я] - 1        еще:  # i не находится в существующем z-боксе            z[я] = match_length(S, 0, я)            если z[я] > 0:                л = я                р = я + z[я] - 1    вернуть zdef bad_character_table(S: ул) -> Список[Список[int]]:    """    Создает R для S, который представляет собой массив, индексированный позицией некоторого символа c в    Английский алфавит. При этом индекс в R представляет собой массив длины | S | +1, определяющий для каждого    индекс i в S (плюс индекс после S) следующее местоположение символа c, встречающееся при    обход S справа налево, начиная с i. Это используется для поиска в постоянное время    для правила плохого символа в алгоритме поиска строки Бойера-Мура, хотя он    гораздо больший размер, чем решения с непостоянным временем.    """    если len(S) == 0:        вернуть [[] для а в ассортимент(ALPHABET_SIZE)]    р = [[-1] для а в ассортимент(ALPHABET_SIZE)]    альфа = [-1 для а в ассортимент(ALPHABET_SIZE)]    для я, c в перечислять(S):        альфа[алфавит_индекс(c)] = я        для j, а в перечислять(альфа):            р[j].добавить(а)    вернуть рdef good_suffix_table(S: ул) -> Список[int]:    """    Создает L для S, массива, используемого в реализации правила сильного хорошего суффикса.    L [i] = k, самая большая позиция в S такая, что S [i:] (суффикс S, начинающийся с i) соответствует    суффикс S [: k] (подстрока в S, оканчивающаяся на k). Используемый в Бойе-Муре, L дает сумму    сдвинуть P относительно T так, чтобы ни один экземпляр P в T не пропускался, и суффикс P [: L [i]]    совпадает с подстрокой T, совпадающей с суффиксом P в предыдущей попытке сопоставления.    В частности, если несоответствие произошло в позиции i-1 в P, величина сдвига задается    уравнением len (P) - L [i]. В случае, когда L [i] = -1, используется таблица полной смены.    Поскольку имеют значение только правильные суффиксы, L [0] = -1.    """    L = [-1 для c в S]    N = фундаментальный_препроцесс(S[::-1])  # S [:: - 1] переворачивает S    N.обеспечить регресс()    для j в ассортимент(0, len(S) - 1):        я = len(S) - N[j]        если я != len(S):            L[я] = j    вернуть Ldef full_shift_table(S: ул) -> Список[int]:    """    Создает F для S, массива, используемого в частном случае правила хорошего суффикса в методе Бойера-Мура.    алгоритм поиска строки. F [i] - это длина самого длинного суффикса S [i:], который также является    префикс S. В тех случаях, когда он используется, величина сдвига паттерна P относительно    текст T равен len (P) - F [i] для несоответствия, возникающего в i-1.    """    F = [0 для c в S]    Z = фундаментальный_препроцесс(S)    самый длинный = 0    для я, zv в перечислять(перевернутый(Z)):        самый длинный = Максимум(zv, самый длинный) если zv == я + 1 еще самый длинный        F[-я - 1] = самый длинный    вернуть Fdef string_search(п, Т) -> Список[int]:    """    Реализация алгоритма поиска строки Бойера-Мура. Это находит все вхождения P    в T, и включает в себя множество способов предварительной обработки шаблона для определения оптимального    количество, чтобы сместить строку и пропустить сравнения. На практике он выполняется за O (m) (и даже    сублинейный) время, где m - длина T. Эта реализация выполняет регистронезависимую    поиск по алфавитным символам ASCII, без пробелов.    """    если len(п) == 0 или len(Т) == 0 или len(Т) < len(п):        вернуть []    совпадения = []    # Предварительная обработка    р = bad_character_table(п)    L = good_suffix_table(п)    F = full_shift_table(п)    k = len(п) - 1      # Представляет выравнивание конца P относительно T    previous_k = -1     # Представляет выравнивание на предыдущей фазе (правило Галиля)    в то время как k < len(Т):        я = len(п) - 1  # Символ для сравнения в P        час = k           # Символ для сравнения в T        в то время как я >= 0 и час > previous_k и п[я] == Т[час]:  # Совпадений, начиная с конца P            я -= 1            час -= 1        если я == -1 или час == previous_k:  # Найдено совпадение (правило Галила)            совпадения.добавить(k - len(п) + 1)            k += len(п) - F[1] если len(п) > 1 еще 1        еще:  # Нет совпадений, сдвиг на максимум плохих символов и хороших суффиксов            char_shift = я - р[алфавит_индекс(Т[час])][я]            если я + 1 == len(п):  # Несоответствие произошло с первой попытки                суффикс_шифт = 1            Элиф L[я + 1] == -1:  # Соответствующий суффикс не появляется нигде в P                суффикс_шифт = len(п) - F[я + 1]            еще:               # Соответствующий суффикс появляется в P                суффикс_шифт = len(п) - 1 - L[я + 1]            сдвиг = Максимум(char_shift, суффикс_шифт)            previous_k = k если сдвиг >= я + 1 еще previous_k  # Правило Галила            k += сдвиг    вернуть совпадения

#включают <stdint.h>#включают <stddef.h>#включают <stdbool.h>#включают <stdlib.h>#define ALPHABET_LEN 256#define max (a, b) ((a // ПРАВИЛО ПЛОХОГО ХАРАКТЕРА.// таблица delta1: delta1 [c] содержит расстояние между последними// символ pat и крайнее правое вхождение c в pat.//// Если c не встречается в pat, тогда delta1 [c] = patlen.// Если c находится в строке [i] и c! = Pat [patlen-1], мы можем безопасно сдвинуть i// через delta1 [c], которое является минимальным расстоянием, необходимым для смещения// пошлите вперед, чтобы строка [i] выровнялась с некоторым символом в pat.// c == pat [patlen-1], возвращающий ноль, касается только BMH, который// не имеет delta2. В таком случае BMH принимает значение patlen.// Мы следуем этому выбору вместо исходного 0, потому что он пропускает//   Больше. (правильность?)//// Этот алгоритм работает в алфавитном порядке + время.пустота make_delta1(ptrdiff_t *дельта1, uint8_t *погладить, size_t Патлен) {    для (int я=0; я < ALPHABET_LEN; я++) {        дельта1[я] = Патлен;    }    для (int я=0; я < Патлен-2; я++) {        дельта1[погладить[я]] = Патлен-1 - я;    }}// истина, если суффикс слова, начинающегося с слова [pos], является префиксом// словаbool is_prefix(uint8_t *слово, size_t язык, ptrdiff_t позиция) {    int суффикслен = язык - позиция;    // здесь также можно использовать библиотечную функцию strncmp ()    // вернуть ! strncmp (слово, & слово [позиция], суффикслен);    для (int я = 0; я < суффикслен; я++) {        если (слово[я] != слово[позиция+я]) {            вернуть ложный;        }    }    вернуть правда;}// длина самого длинного суффикса слова, оканчивающегося словом [pos].// длина_суффикса ("dddbcabc", 8, 4) = 2size_t суффикс_длина(uint8_t *слово, size_t язык, ptrdiff_t позиция) {    size_t я;    // увеличиваем длину суффикса i до первого несоответствия или начала    // слова    для (я = 0; (слово[позиция-я] == слово[язык-1-я]) && (я < позиция); я++);    вернуть я;}// ПРАВИЛО ХОРОШЕГО СУФФИКСА.// таблица delta2: учитывая несоответствие в pat [pos], мы хотим выровнять// следующее возможное полное совпадение может быть основано на том, что мы// знать о пат [pos + 1], чтобы пат [patlen-1].//// В случае 1:// pat [pos + 1] to pat [patlen-1] не встречается в другом месте в pat,// следующее вероятное совпадение начинается с несовпадения или после него.// Если в подстроке pat [pos + 1 .. patlen-1] лежит префикс// пат, следующее правдоподобное совпадение здесь (если есть несколько// префиксы в подстроке, выбираем самый длинный). В противном случае// следующее вероятное совпадение начинается после символа, выровненного с// пат [патлен-1].//// В случае 2:// pat [pos + 1] to pat [patlen-1] действительно встречается в другом месте в pat. В// несоответствие говорит нам, что мы не смотрим на конец совпадения.// Однако мы можем смотреть в середину матча.//// Первый цикл, который обрабатывает случай 1, аналогичен// таблица KMP, адаптированная для «обратного» порядка сканирования с// дополнительное ограничение, что подстроки он считает// все потенциальные префиксы суффиксы. В худшем случае// pat состоит из одинаковых повторяющихся букв, поэтому каждый суффикс// префикс. Однако одного этого цикла недостаточно:// Предположим, что pat - это «ABYXCDBYX», а текст - «..... ABYXCDEYX».// Мы сопоставим X, Y и найдем B! = E. Нет префикса pat// в суффиксе "YX", поэтому первый цикл говорит нам пропустить вперед// на 9 знаков.// Хотя внешне похожа на таблицу KMP, таблица KMP// полагается на информацию о начале частичного совпадения// чего нет в алгоритме BM.//// Второй цикл обращается к случаю 2. Так как суффикс_длина не может быть// уникально, мы хотим взять минимальное значение, которое нам скажет// насколько далеко ближайшее возможное совпадение.пустота make_delta2(ptrdiff_t *дельта2, uint8_t *погладить, size_t Патлен) {    ssize_t п;    size_t last_prefix_index = Патлен-1;    // первый цикл    для (п=Патлен-1; п>=0; п--) {        если (is_prefix(погладить, Патлен, п+1)) {            last_prefix_index = п+1;        }        дельта2[п] = last_prefix_index + (Патлен-1 - п);    }    // второй цикл    для (п=0; п < Патлен-1; п++) {        size_t стройный = суффикс_длина(погладить, Патлен, п);        если (погладить[п - стройный] != погладить[Патлен-1 - стройный]) {            дельта2[Патлен-1 - стройный] = Патлен-1 - п + стройный;        }    }}// Возвращает указатель на первое совпадение.// См. Также glibc memmem () (не BM) и std :: boyer_moore_searcher (первое совпадение).uint8_t* Boyer_moore (uint8_t *строка, size_t Stringlen, uint8_t *погладить, size_t Патлен) {    ptrdiff_t дельта1[ALPHABET_LEN];    ptrdiff_t дельта2[Патлен]; // C99 VLA    make_delta1(дельта1, погладить, Патлен);    make_delta2(дельта2, погладить, Патлен);    // Пустой шаблон нужно рассматривать особо    если (Патлен == 0) {        свободный(дельта2);        вернуть строка;    }    size_t я = Патлен - 1;        // str-idx    в то время как (я < Stringlen) {        ptrdiff_t j = Патлен - 1; // pat-idx        в то время как (j >= 0 && (строка[я] == погладить[j])) {            --я;            --j;        }        если (j < 0) {            свободный(дельта2);            вернуть &строка[я+1];        }        ptrdiff_t сдвиг = Максимум(дельта1[строка[я]], дельта2[j]);        я += сдвиг;    }    свободный(дельта2);    вернуть ЗНАЧЕНИЕ NULL;}

    /**     * Возвращает индекс в этой строке первого вхождения     * указанная подстрока. Если это не подстрока, верните -1.     *     * Galil не существует, потому что он генерирует только одно совпадение.     *     * @param haystack Строка для сканирования     * @param Needle Целевая строка для поиска     * @return Начальный индекс подстроки     */    общественный статический int индекс(char[] стог сена, char[] игла) {        если (игла.длина == 0) {            вернуть 0;        }        int charTable[] = makeCharTable(игла);        int offsetTable[] = makeOffsetTable(игла);        для (int я = игла.длина - 1, j; я < стог сена.длина;) {            для (j = игла.длина - 1; игла[j] == стог сена[я]; --я, --j) {                если (j == 0) {                    вернуть я;                }            }            // i + = Needle.length - j; // Для наивного метода            я += Математика.Максимум(offsetTable[игла.длина - 1 - j], charTable[стог сена[я]]);        }        вернуть -1;    }    /**     * Делает таблицу переходов на основе информации о несовпадающих символах.     */    частный статический int[] makeCharTable(char[] игла) {        окончательный int ALPHABET_SIZE = символ.MAX_VALUE + 1; // 65536        int[] Таблица = новый int[ALPHABET_SIZE];        для (int я = 0; я < Таблица.длина; ++я) {            Таблица[я] = игла.длина;        }        для (int я = 0; я < игла.длина - 2; ++я) {            Таблица[игла[я]] = игла.длина - 1 - я;        }        вернуть Таблица;    }    /**     * Создает таблицу переходов на основе смещения сканирования, при котором возникает несоответствие.     * (правило плохого персонажа).     */    частный статический int[] makeOffsetTable(char[] игла) {        int[] Таблица = новый int[игла.длина];        int lastPrefixPosition = игла.длина;        для (int я = игла.длина; я > 0; --я) {            если (isPrefix(игла, я)) {                lastPrefixPosition = я;            }            Таблица[игла.длина - я] = lastPrefixPosition - я + игла.длина;        }        для (int я = 0; я < игла.длина - 1; ++я) {            int стройный = суффиксДлина(игла, я);            Таблица[стройный] = игла.длина - 1 - я + стройный;        }        вернуть Таблица;    }    /**     * Является ли игла [p: end] префиксом иглы?     */    частный статический логический isPrefix(char[] игла, int п) {        для (int я = п, j = 0; я < игла.длина; ++я, ++j) {            если (игла[я] != игла[j]) {                вернуть ложный;            }        }        вернуть правда;    }    /**     * Возвращает максимальную длину подстроки, заканчивающейся на p и являющейся суффиксом.     * (правило хорошего суффикса)     */    частный статический int суффиксДлина(char[] игла, int п) {        int len = 0;        для (int я = п, j = игла.длина - 1;                 я >= 0 && игла[я] == игла[j]; --я, --j) {            len += 1;        }        вернуть len;    }

Варианты

В Алгоритм Бойера – Мура – ​​Хорспула представляет собой упрощение алгоритма Бойера – Мура, использующее только правило плохих символов.

В Алгоритм Апостолико – Джанкарло ускоряет процесс проверки совпадения при заданном выравнивании, пропуская явные сравнения символов. При этом используется информация, полученная во время предварительной обработки шаблона, в сочетании с длинами совпадений суффиксов, записанными при каждой попытке сопоставления. Для хранения длин совпадений суффиксов требуется дополнительная таблица, размер которой равен размеру искомого текста.

В Алгоритм Раита улучшает производительность алгоритма Бойера-Мура-Хорспула. Шаблон поиска конкретной подстроки в данной строке отличается от алгоритма Бойера-Мура-Хорспула.

Заметки

использованная литература

внешние ссылки

• Оригинальная статья по алгоритму Бойера-Мура
• Пример алгоритма Бойера-Мура с домашней страницы Дж. Стротер Мур, соавтор алгоритма
• Статья Ричарда Коула 1991 года, доказывающая линейность времени выполнения