418
правок
Изменения
м
→Правило сдвига плохого символа
В таблице плохих символов указывается последняя позиция в шаблоне (исключая последнюю букву) каждого из символов алфавита. Для всех символов, не вошедших в шаблон, пишем <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>.]]
