418
правок
Изменения
Нет описания правки
[[Файл:boyer-moore-algorithm-4.gif|450px|thumb|center|'''Сдвиг плохого символа''', символ <tex>b</tex> не входит в <tex>x</tex>.]]
Обратите внимание, что сдвиг плохого символ может быть отрицательным, таким образом для сдвига окна сравнения алгоритм Бойера-Мура использует значение, равное максимуму между сдвигом хорошего суффикса и сдвига плохого символа. Более формально две функции сдвигов определяются следующим образом:
Пусть значения функции сдвига хорошего суффикса хранятся в таблице <tex>bmGs</tex> размером <tex>m+1</tex>.
Определим два условия:
* <tex>Cs(i, s)</tex>: для каждого <tex>k</tex> такого, что <tex>i < k < m</tex> выполняется <tex>s \geqslant k</tex> или <tex>x[k-s]=x[k]</tex>
* <tex>Co(i, s)</tex>: если <tex>s < i</tex>, то выполняется <tex>x[i-s] \neq x[i]</tex>
Тогда для всех <tex>i</tex> таких, что <tex>0 \leqslant i < m</tex> выполняется <tex>bmGs[i+1]=\min\{s > 0 : Cs(i, s) and Co(i, s)\}</tex>. А значение <tex>bmGs[0]</tex> определим, как длину периода шаблона <tex>x</tex>.
Для вычисления bmGs будем использовать таблицу <tex>suff</tex>, определенную так:
для всех <tex>i</tex> таких, что <tex>1 \leqslant i < m</tex> выполняется <tex>suff[i]=\max\{k : x[i-k+1 .. i]=x[m-k .. m-1]\}</tex>
==Псевдо-код==
