418
правок
Изменения
м
Нет описания правки
Алгоритм Бойера-Мура, разработанный двумя учеными – Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке.
Важной особенностью алгоритма является то, что он выполняет сравнения справа налево в отличии от многих других алгоритмов.
==Асимптотики==
Фаза предварительных вычислений требует <tex>O(m + sigma)</tex> времени и памяти
В худшем случае поиск требует <tex>O(m \cdot n)</tex> сравнений.
В лучшем случае требует <tex>O(n / m)</tex> сравнений.
В 1991 году Р.Коул доказал следующую теорему:
{{Теорема
|author=Richard Cole
|statement=В худшем случае требуется <tex>O(3 \cdot n)</tex> сравнений в случае шаблона с периодом равным длине самого шаблона.
|proof=Доказательство [http://www.cs.nyu.edu/cs/faculty/cole/papers/CHPZ95.ps]
}}
==Алгоритм==
==Псевдо-код==
==Улучшения==
