418
правок
Изменения
Нет описания правки
Пусть <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 .. m-1]=y[i+j+1 .. j+m-1]=u</tex> и <tex>x[i] \neq y[i+j]</tex>, т.е. и <tex>m - i - 1</tex> символов шаблона уже совпало.
===Правило сдвига хорошего суффикса===
===Правило сдвига плохого символа===
В таблице плохих символов указывается последняя позиция в шаблоне (исключая последнюю букву) каждого из символов алфавита. Для всех символов, не вошедших в шаблон, пишем <tex>m</tex>. Предположим, что у нас не совпал символ <tex>c</tex> из текста на очередном шаге с символом из шаблона. Очевидно, что в таком случае мы можем сдвинуть шаблон до первого вхождения этого символа <tex>c</tex> в шаблоне, т.к. потому что совпадений других символов точно не может быть. Если в шаблоне такого символа нет, то можно можно сдвинуть весь шаблон полностью.
Если символ исходного текста <tex>y[i + j]</tex> встречается в шаблоне <tex>x</tex>, то происходит его выравнивание с его самым правым появлением в подстроке <tex>x[0 .. m-2]</tex>.
[[Файл:boyer-moore-algorithm-3.png|450px|thumb|center|'''Сдвиг плохого символа''', символ <tex>a</tex> входит в <tex>x</tex>.]]
Если <tex>y[i+j]</tex> не встречается в шаблоне <tex>x</tex>, то ни одно вхождение <tex>x</tex> в <tex>y</tex> не может включать в себя <tex>y[i+j]</tex>, и левый конец окна сравнения совмещен с символом непосредственно идущим после <tex>y[i+j]</tex>, т.е. то есть символ <tex>y[i+j+1]</tex>.
[[Файл:boyer-moore-algorithm-4.png|450px|thumb|center|'''Сдвиг плохого символа''', символ <tex>b</tex> не входит в <tex>x</tex>.]]
'''if''' i < 0
OUTPUT(j) <font color=green>// Найдена подстрока в позиции j</font>
j += bmGs[0] <font color=green>//Очевидно, что можем сделать сдвиг на период, т.к. потому что там явно не будет совпадений.</font>
'''else'''
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i)
* В худшем случае поиск требует <tex>O(m \cdot n)</tex> сравнений.
* В лучшем случае требует <tex>O(n / m)</tex> сравнений.
'''Пример:'''
Исходный текст <tex>bb..bb</tex> и шаблон <tex>abab..abab</tex>. Из-за того, что все символы <tex>b</tex> из текста повторяются в шаблоне <tex>m / 2</tex> раз, эвристика хорошего суффикса будет пытаться сопоставить шаблон в каждой позиции (суммарно, <tex>n</tex> раз), а эвристика плохого символа в каждой позиции будет двигать строку <tex>m / 2</tex> раз. Итого, <tex>O(n \cdot m)</tex>.
где <tex>n</tex> {{---}} длина исходного текста, <tex>m</tex> {{---}} длина шаблона, <tex>\sigma</tex> {{---}} размер алфавита.
* На больших алфавитах (относительно длины шаблона) алгоритм чрезвычайно быстрый и требует намного меньше памяти относительно [[Алгоритм Ахо-Корасик|алгоритма Ахо-Корасик]].
* Алгоритм проще большинства алгоритмов поиска (при некоторых реализациях объем кода сравним с [[Наивный_алгоритм_поиска_подстроки_в_строке|наивным поиском]])
* Позволяет добавить множество модификаций, таких как поиск подстроки, включающей ''любой символ (?)'' (но для реализации ''множества символов (*)'' не походит, т.к. так как длина шаблона должна быть известна заранее).
===Недостатки===
