251
правка
Изменения
Нет описания правки
'''Алгоритм Бойера-Мура за линейное время(Турбо-алгоритм)''' (англ. ''Turbo Boyer-Moore) является улучшением [[Алгоритм Бойера-Мура|алгоритма Бойера-Мура]]. Алгоритм, разработанный группой учёных во главе с М.Крочемором предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае.
==Алгоритм==
Турбо-алгоритм Бойера-Мура не нуждается в дополнительном препроцессинге и требует только постоянную дополнительную память относительно оригинального алгоритма Бойера-Мура. Он состоит в запоминании сегмента текста, который соответствует суффикс шаблона во время последней попытки (и только тогда, когда сдвиг хорошего суффикса был выполнен).
* [http://www-igm.univ-mlv.fr/~lecroq/string/node15.html#SECTION00150 Turbo Boyer-Moore algorithm]
* [http://algolist.manual.ru/search/esearch/turbo_bm.php Турбо Боуер-Мур]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Поиск подстроки в строке]]
[[Категория:Точный поиск]]
