Алгоритм Бойера-Мура

Алгоритм Бойера-Мура, разработанный двумя учеными – Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Важной особенностью алгоритма является то, что он выполняет сравнения справа налево в отличии от многих других алгоритмов.

Алгоритм Бойера-Мура считается наиболее эффективным алгоритмом поиска шаблонов в стандартных приложениях и командах, таких как Ctrl+F в браузерах и текстовых редакторах.

Асимптотики

Фаза предварительных вычислений требует [math]O(m + sigma)[/math] времени и памяти В худшем случае поиск требует [math]O(m \cdot n)[/math] сравнений. В лучшем случае требует [math]O(n / m)[/math] сравнений.

В 1991 году Р.Коул доказал следующую теорему:

Теорема (Richard Cole):

В худшем случае требуется [math]O(3 \cdot n)[/math] сравнений в случае шаблона с периодом равным длине самого шаблона.

Доказательство:

[math]\triangleright[/math]

Доказательство [1]

[math]\triangleleft[/math]

Алгоритм

Алгоритм сравнивает символы шаблона ([math]y[/math]) справа налево, начиная с самого правого, один за другим с символами исходной строки ([math]x[/math]). В случае несовпадения какого-либо символа (или полного совпадения всего шаблона) он использует две предварительно вычисляемых функций, чтобы сдвинуть позицию для начала сравнения вправо.

Пусть [math]|y|=n[/math] и [math]|x|=m[/math].

Предположим, что в процессе сравнения возникает несовпадение между символом [math]x[i]=a[/math] шаблона и символом [math]y[i+j]=b[/math] исходного текста при проверке в позиции [math]j[/math]. Тогда [math]x[i+1 .. m-1]=y[i+j+1 .. j+m-1]=u[/math] и [math]x[i] \neq y[i+j][/math]

Ссылки

• Википедия:Алгоритм Бойера-Мура
• Википедия:Алгоритм Бойера-Мура-Хорспула
• Wikipedia:Boyer–Moore string search algorithm
• [2]