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

Алгоритм Бойера-Мура, разработанный двумя учеными – Бойером (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]