Изменения

Перейти к: навигация, поиск

Алгоритм Бойера-Мура

19 байт убрано, 20:28, 10 мая 2014
м
Формальное определение
===Формальное определение===
Таким образом для сдвига позиции начала сравнения алгоритм Бойера-Мура использует выбирает между двумя эвристическими функциями, называемыми эвристиками хорошего суффикса и плохого символа (иногда они называются эвристиками совпавшего суффикса и стоп-символа). Так как функции эвристические, то выбор между ними простой {{---}} ищется такое итоговое значение, чтобы мы не проверяли максимальное число позиций и при этом нашли все подстроки равные шаблону. Исходя из вышесказанных ранее приведенных свойств этих функций можно брать берется значение равное максимуму между сдвигом хорошего суффикса и сдвига сдвигом плохого символа.
Теперь определим две функции сдвигов более формально следующим образом:
418
правок

Навигация