Алгоритм Бойера-Мура — различия между версиями
Kabanov (обсуждение | вклад) (Новая страница: «==Алгоритм== ==Псевдо-код== ==Улучшения==») |
Kabanov (обсуждение | вклад) м |
||
| Строка 1: | Строка 1: | ||
| + | Алгоритм Бойера-Мура, разработанный двумя учеными – Бойером (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] | ||
| + | }} | ||
| + | |||
==Алгоритм== | ==Алгоритм== | ||
==Псевдо-код== | ==Псевдо-код== | ||
==Улучшения== | ==Улучшения== | ||
Версия 17:33, 4 мая 2014
Алгоритм Бойера-Мура, разработанный двумя учеными – Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Важной особенностью алгоритма является то, что он выполняет сравнения справа налево в отличии от многих других алгоритмов.
Содержание
Асимптотики
Фаза предварительных вычислений требует времени и памяти В худшем случае поиск требует сравнений. В лучшем случае требует сравнений.
В 1991 году Р.Коул доказал следующую теорему:
| Теорема (Richard Cole): |
В худшем случае требуется сравнений в случае шаблона с периодом равным длине самого шаблона. |
| Доказательство: |
| Доказательство [1] |
