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