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