418
правок
Изменения
Нет описания правки
Операция '''сдвига хорошего суффикса''' состоит в выравнивании подстроки <tex>u</tex> с его самым правым вхождением в <tex>x</tex>, что идет впереди символа, отличного от <tex>x[i]</tex>.
[[Файл:boyer-moore-algorithm-1.gif|450px|thumb|center|The good-suffix shift'''Сдвиг хорошего суффикса''', подстрока <tex>u re-occurs preceded by a character </tex> повторно встречается до символа <tex>c different from </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|The good-suffix shift'''Сдвиг хорошего суффикса''', only a suffix of только суффикс подстроки <tex>u re-occurs in </tex> повторно встречается в <tex>x</tex>.]]
Операция '''сдвига плохого символа''' состоит в выравнивании символа исходного текста <tex>у[i + j]</tex> с его самым правого правым появлением в <tex>x[0 .. m-2]</tex>.
[[Файл:boyer-moore-algorithm-3.gif|450px|thumb|center|The bad'''Сдвиг плохого символа''', символ <tex>a</tex> входит в <tex>x</tex>.]] Если <tex>y[i+j]</tex> не встречается в шаблоне x, то ни одно вхождение x в y не может включать в себя <tex>y[i+j]</tex>, и левый конец окна сравнения совмещен с символом непосредственно идущим после <tex>y[i+j]</tex>, т.е. <tex>y[i+j+1]</tex>. [[Файл:boyer-character shiftmoore-algorithm-4.gif|450px|thumb|center|'''Сдвиг плохого символа''', a occurs in символ <tex>b</tex> не входит в <tex>x</tex>.]]
==Псевдо-код==
