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

Материал из Викиконспекты
Перейти к: навигация, поиск

Алгоритм Бойера-Мура, разработанный двумя учеными – Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Важной особенностью алгоритма является то, что он выполняет сравнения справа налево в отличии от многих других алгоритмов.

Асимптотики

Фаза предварительных вычислений требует [math]O(m + sigma)[/math] времени и памяти В худшем случае поиск требует [math]O(m \cdot n)[/math] сравнений. В лучшем случае требует [math]O(n / m)[/math] сравнений.

В 1991 году Р.Коул доказал следующую теорему:

Теорема (Richard Cole):
В худшем случае требуется [math]O(3 \cdot n)[/math] сравнений в случае шаблона с периодом равным длине самого шаблона.
Доказательство:
[math]\triangleright[/math]
Доказательство [1]
[math]\triangleleft[/math]

Алгоритм

Псевдо-код

Улучшения