418
правок
Изменения
м
Более формально Таким образом для сдвига позиции начала сравнения алгоритм Бойера-Мура использует выбирает между двумя эвристическими функциями, называемыми эвристиками хорошего суффикса и плохого символа (иногда они называются эвристиками совпавшего суффикса и стоп-символа). Так как функции эвристические, то выбор между ними простой {{---}} ищется такое итоговое значение, чтобы мы не проверяли максимальное число позиций и при этом нашли все подстроки равные шаблону. Исходя из вышесказанных свойств этих функций можно брать значение равное максимуму между сдвигом хорошего суффикса и сдвига плохого символа. Теперь определим две функции сдвигов определяются более формально следующим образом:
→Алгоритм
[[Файл:boyer-moore-algorithm-4.png|450px|thumb|center|'''Сдвиг плохого символа''', символ <tex>b</tex> не входит в <tex>x</tex>.]]
Обратите внимание, что сдвиг плохого символа может быть отрицательным, таким образом для сдвига окна сравнения алгоритм Бойера-Мура использует значение, равное максимуму между сдвигом хорошего суффикса и сдвига плохого символа.
===Формальное определение===
Пусть значения функции сдвига хорошего суффикса хранятся в массиве <tex>bmGs</tex> размером <tex>m+1</tex>.
