Алгоритм Бойера-Мура — различия между версиями
Kabanov (обсуждение | вклад) м |
Kabanov (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
Алгоритм Бойера-Мура, разработанный двумя учеными – Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. | Алгоритм Бойера-Мура, разработанный двумя учеными – Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. | ||
Важной особенностью алгоритма является то, что он выполняет сравнения справа налево в отличии от многих других алгоритмов. | Важной особенностью алгоритма является то, что он выполняет сравнения справа налево в отличии от многих других алгоритмов. | ||
| + | |||
| + | Алгоритм сканирует символы шаблона справа налево, начиная с самого правого, один за другим. В случае несовпадения какого-либо символа (или полного совпадения всего шаблона) он использует две предварительно вычисляемых функций, чтобы сдвинуть позицию для начала сравнения вправо. | ||
| + | |||
| + | |||
==Асимптотики== | ==Асимптотики== | ||
| Строка 15: | Строка 19: | ||
==Алгоритм== | ==Алгоритм== | ||
| + | |||
==Псевдо-код== | ==Псевдо-код== | ||
| − | == | + | |
| + | ==Ссылки== | ||
| + | * [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D0%B9%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%9C%D1%83%D1%80%D0%B0 Википедия:Алгоритм Бойера-Мура] | ||
| + | * [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D0%B9%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%9C%D1%83%D1%80%D0%B0_%E2%80%94_%D0%A5%D0%BE%D1%80%D1%81%D0%BF%D1%83%D0%BB%D0%B0 Википедия:Алгоритм Бойера-Мура-Хорспула] | ||
| + | * [http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm Wikipedia:Boyer–Moore string search algorithm] | ||
| + | * [http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140] | ||
Версия 19:49, 5 мая 2014
Алгоритм Бойера-Мура, разработанный двумя учеными – Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Важной особенностью алгоритма является то, что он выполняет сравнения справа налево в отличии от многих других алгоритмов.
Алгоритм сканирует символы шаблона справа налево, начиная с самого правого, один за другим. В случае несовпадения какого-либо символа (или полного совпадения всего шаблона) он использует две предварительно вычисляемых функций, чтобы сдвинуть позицию для начала сравнения вправо.
Содержание
Асимптотики
Фаза предварительных вычислений требует времени и памяти В худшем случае поиск требует сравнений. В лучшем случае требует сравнений.
В 1991 году Р.Коул доказал следующую теорему:
| Теорема (Richard Cole): |
В худшем случае требуется сравнений в случае шаблона с периодом равным длине самого шаблона. |
| Доказательство: |
| Доказательство [1] |
