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

Материал из Викиконспекты
Версия от 21:27, 29 марта 2016; Zemskovk (обсуждение | вклад) (Создано)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Алгоритм

Правило сдвига хорошего суффикса

Турбо сдвиг

Формальное определение

Псевдокод

Асимптотики

Ссылки