418
правок
Изменения
м
→Алгоритм
Операция '''сдвига плохого символа''' состоит в выравнивании символа исходного текста <tex>у[i + j]</tex> с его самым правым появлением в <tex>x[0 .. m-2]</tex>.
[[Файл:boyer-moore-algorithm-3.gifpng|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.gifpng|450px|thumb|center|'''Сдвиг плохого символа''', символ <tex>b</tex> не входит в <tex>x</tex>.]]
Обратите внимание, что сдвиг плохого символа может быть отрицательным, таким образом для сдвига окна сравнения алгоритм Бойера-Мура использует значение, равное максимуму между сдвигом хорошего суффикса и сдвига плохого символа.
