418
правок
Изменения
→Алгоритм
Предположим, что в процессе сравнения возникает несовпадение между символом <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> символов шаблона уже совпало.
[[Файл:boyer-moore-algorithm-1.gif|450px|thumb|center|'''Сдвиг хорошего суффикса''', вся подстрока <tex>u</tex> полностью встречается справа от символа <tex>c</tex>, отличного от символа <tex>a</tex>.]]
Если не существует такого сегментатакой подстроки, то смещение состоит в выравнивании самого длинного суффикса <tex>v</tex> подстроки <tex>y[i+j+1 .. j+m-1]</tex> с соответствующим префиксом <tex>x</tex>.
[[Файл:boyer-moore-algorithm-2.gif|450px|thumb|center|'''Сдвиг хорошего суффикса''', только суффикс подстроки <tex>u</tex> повторно встречается в <tex>x</tex>.]]
===Правило сдвига плохого символа===
В таблице плохих символов указывается последняя позиция в шаблоне (исключая последнюю букву) каждого из символов алфавита. Для всех символов, не вошедших в шаблон, пишем <tex>m</tex>. Предположим, что у нас не совпал символ <tex>c</tex> из текста на очередном шаге с символом из шаблона. Очевидно, что в таком случае мы можем сдвинуть шаблон до первого вхождения этого символа <tex>c</tex> в шаблоне, т.к. совпадений других символов точно не может быть. Если в шаблоне такого символа нет, то можно можно сдвинуть весь шаблон полностью.
Операция '''сдвига плохого символа''' состоит в выравнивании символа исходного текста <tex>у[i + j]</tex> с его самым правым появлением в <tex>x[0 .. m-2]</tex>.
[[Файл:boyer-moore-algorithm-4.gif|450px|thumb|center|'''Сдвиг плохого символа''', символ <tex>b</tex> не входит в <tex>x</tex>.]]
Обратите внимание, что сдвиг плохого символа может быть отрицательным, таким образом для сдвига окна сравнения алгоритм Бойера-Мура использует значение, равное максимуму между сдвигом хорошего суффикса и сдвига плохого символа. ===Формальное определение===Более формально две функции сдвигов определяются следующим образом:
Пусть значения функции сдвига хорошего суффикса хранятся в массиве <tex>bmGs</tex> размером <tex>m+1</tex>.
