Изменения
→Псевдокод: неправильный код, пусть пересмотрят нормальные программисты, бред написан
'''Алгоритм Бойера-Мура''', разработанный двумя учеными {{---}} Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Важной особенностью алгоритма является то, что он выполняет сравнения в шаблоне справа налево в отличии отличие от многих других алгоритмов.
Алгоритм Бойера-Мура считается наиболее эффективным алгоритмом поиска шаблонов в стандартных приложениях и командах, таких как Ctrl+F в браузерах и текстовых редакторах.
Алфавит обозначим буквой <tex>\Sigma</tex>.
Пусть <tex>|y|=n</tex>, <tex>|x|=m</tex> и <tex>|\Sigma|=\sigma</tex>.
Предположим, что в процессе сравнения возникает несовпадение между символом <tex>x[i]=a</tex> шаблона и символом <tex>y[i+j]=b</tex> исходного текста при проверке в позиции <tex>j</tex>. Тогда <tex>x[i+1 \dots m-1]=y[i+j+1 \dots j+m-1]=u</tex> и <tex>x[i] \neq y[i+j]</tex>, и <tex>m - i - 1</tex> символов шаблона уже совпало.
* <tex>\mathrm{Co}(i, s)</tex>: если <tex>s < i</tex>, то выполняется <tex>x[i-s] \neq x[i]</tex>
Тогда для всех <tex>i</tex> таких, что <tex>0 \leqslant i < m</tex> выполняется <tex>bmGs[i+1]=\min\{s > 0 : \mathrm{Cs}(i, s)\ and\wedge\ \mathrm{Co}(i, s)\}</tex>.
А значение <tex>bmGs[0]</tex> определим, как длину периода шаблона <tex>x</tex>.
Сдвиги плохих символов будем хранить в массиве <tex>bmBc</tex> размером <tex>\sigma</tex>.
Для каждого символа <tex>c</tex> из <tex>\Sigma</tex>: <tex>bmBc[c] = \begin{cases}
\min\{i : 1 \leqslant i < m-1\ and\wedge\ x[m-1-i]=c\}, & \mbox{if } c \in x\\
m, & \mbox{otherwise}
\end{cases}</tex>
==Псевдокод==
Константой <tex>|\Sigma|=\sigma=ASIZE</tex> обозначим размер нашего алфавита.
Функция для вычисления таблицы сдвигов плохих символов. Она будет равна длине шаблона для всех символов, которые не встречаются в шаблоне, и порядковому номеру с конца для остальных (кроме последнего, для него тоже берется длина шаблона). Вычисляется прямо по определению за <tex>O(m+\sigma)</tex>. '''int'''[] preBmBc('''char'''[m] x, '''int''' m): '''int''' table<tex>[ASIZE</tex> <tex>|\Sigma|</tex> <tex>]</tex>
<font color=green>// Заполняем значением по умолчанию, равным длине шаблона</font>
'''for''' i = 0 .. ASIZE <tex>|\Sigma|</tex> - 1
table[i] = m
<font color=green>// Вычисление функции по определению</font>
Функция, проверяющая, что подстрока <tex>x[p \dots m - 1]</tex> является префиксом шаблона <tex>x</tex>. Требует <tex>O(m - p)</tex> времени.
'''boolean''' isPrefix('''char'''[m] x, '''int''' m, '''int''' p):
'''int''' j = 0
'''for''' i = p .. m - 1
'''return''' true
Функция, возвращающая для позиции <tex>p</tex> длину максимальной подстроки, которая является суффиксом шаблона <tex>x</tex>. Требует <tex>O(m - p)</tex> времени.//здесь неправильно, нет смысла сравнивать элементы ШАБЛОНА С САМИМ СОБОЙ '''int''' suffixLength('''char'''[m] x, '''int''' m, '''int''' p):
'''int''' len = 0
'''int''' i = p
'''int''' j = m - 1
'''while''' i <tex>\geqslant</tex>= 0 '''and''' x[i] == x[j] ++len += 1
--i
--j
Функция для вычисления сдвигов хороших суффиксов. Требует <tex>O(m)</tex> времени, несмотря на циклы в вызываемых функциях, из-за того, что каждый внутренний цикл в худшем случае будет выполняться на каждой позиции <tex>i</tex> не больше, чем <tex>i</tex> раз. Получается натуральный ряд, сумма <tex>m</tex> первых членов которого <tex dpi="150">\frac{m \cdot (m - 1)}{2}</tex>. Следовательно, получается оценка по времени <tex>O(m^2)</tex>.
'''int'''[] preBmGs('''char'''[m] x, '''int''' m):
'''int''' table[m]
'''int''' lastPrefixPosition = m
'''for''' i = m - 1 .. 0
<font color=green>// Если подстрока x[i+1..m-1] является префиксом, то запомним её начало</font>
'''if''' isPrefix(x, m, i + 1)
lastPrefixPosition = i + 1
table[m - 1 - i] = lastPrefixPosition - i + m - 1
<font color=green>// Вычисление функции по определению</font>
'''for''' i = 0 .. m - 2
'''int''' slen = suffixLength(x, m, i)
table[slen] = m - 1 - i + slen
'''return''' table
Основная функция алгоритма Бойера-Мура
'''function''' BM('''char'''[n] y, '''char'''[m] x): '''vector <int>''' n = length(y) '''vector <int>''' m answer <font color= length(x)green>// вектор, содержащий все вхождения подстроки в строку</font>
'''if''' m == 0
answer.pushBack(-1) <font color=green>// Искомая подстрока является пустой</font> '''return'''answer
<font color=green>//Предварительные вычисления</font> '''int''' bmBc<tex>[</tex> <tex>|\Sigma|</tex> <tex>] </tex> bmBc = preBmBc(x, m) '''int''' bmGs[m] bmGs = preBmGs(x, m)
<font color=green>//Поиск подстроки</font>
'''for''' i = m - 1 .. n - 1
'''int''' j = m - 1
'''while''' x[j] == y[i]
'''if''' j == 0
--i
--j
i += MAXmax(bmGs[m - 1 - j], bmBc[y[i]]) '''if''' (answer == <tex> \varnothing </tex>) answer.pushBack(-1) <font color=green>// Искомая подстрока не найдена</font> '''return''' answer ==Пример==Пусть нам дана строка <tex>y = GCATCGCAGAGAGTATACAGTACG</tex> и образец <tex>x=GCAGAGAG</tex>. Построим массивы <tex>bmBc</tex> и <tex>bmGs</tex> : [[Файл:RaitaPre.png|250px]] [[Файл:Crochemore.png|300px]] Рассмотрим шаги алгоритма: {| class = "wikitable"! Изображение !! <tex>(j, bmGs[y[j]])</tex> !! Описание|-align="center"|[[Файл:BMexample1.png|550px]]|<tex>(7, 1)</tex>|Сравниванием последние символы, они неравны, поэтому сдвигаемся на <tex> bmGs[y[j]]</tex>, где <tex>y[j]</tex> {{---}} это не совпавший символ. В данном случае <tex>y[j]=7</tex>, а <tex> bmGs[7]= 1</tex>.|-align="center"|[[Файл:BMexample2.png|550px]]|<tex>(8, 4)</tex>|Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся на <tex> bmGs[5]= 4</tex>.|-align="center"|[[Файл:BMexample3.png|550px]]|<tex>(12, 7)</tex>|Последние символы совпали, сравниваем далее. Строчка найдена. Продолжаем работу и сдвигаемся на <tex> bmGs[0]= 7</tex>.|-align="center"|[[Файл:BMexample4.png|550px]]|<tex>(19, 4)</tex>|Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся на <tex> bmGs[5]= 4</tex>.|-align="center"|[[Файл:BMexample5.png|550px]]|<tex>(23, 7)</tex>|Последние символы совпали, предпоследние различны. Алгоритм закончил работу.|-align="center"|} В итоге, чтобы найти одно вхождение образца длиной <tex>m = 8</tex> в образце длиной <tex>n = 24</tex>, нам понадобилось <tex>17</tex> сравнений символов.
==Асимптотики==
* Фаза предварительных вычислений требует <tex>O(m^2 + \sigma)</tex> времени и памяти.
* В худшем случае поиск требует <tex>O(m \cdot n)</tex> сравнений.
* В лучшем случае требует <tex > \Omega\left(\dfrac{n / }{m} \right)</tex> сравнений.
'''Пример:'''
Исходный текст <tex>bb \dots bb</tex> и шаблон <tex>abab \dots abab</tex>. Из-за того, что все символы <tex>b</tex> из текста повторяются в шаблоне <tex>\dfrac{m / }{2}</tex> раз, эвристика хорошего суффикса будет пытаться сопоставить шаблон в каждой позиции (суммарно, <tex>n</tex> раз), а эвристика плохого символа в каждой позиции будет двигать строку <tex>\dfrac{m / }{2}</tex> раз. Итого, <tex>O(n \cdot m)</tex>.
где <tex>n</tex> {{---}} длина исходного текста, <tex>m</tex> {{---}} длина шаблона, <tex>\sigma</tex> {{---}} размер алфавита.
* На искусственно подобранных неудачных текстах скорость алгоритма Бойера-Мура серьёзно снижается.
==СсылкиИсточники информации==
* [[wikipedia:ru:Алгоритм_Бойера_—_Мура|Википедия {{---}} Алгоритм Бойера-Мура]]
* [[wikipedia:ru:Алгоритм_Бойера_—_Мура_—_Хорспула|Википедия {{---}} Алгоритм Бойера-Мура-Хорспула]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Поиск подстроки в строке]]
[[Категория: Точный поиск]]
