251
правка
Изменения
Нет описания правки
'''Алгоритм Бойера-Мура за линейное время(Турбо-алгоритм)''' является улучшением [[Алгоритм Бойера-Мура|алгоритма Бойера-Мура]]. Алгоритм, разработанный группой учёных во главе с М.Крочемором предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае.
==Алгоритм==
Турбо-алгоритм Бойера-Мура не нуждается в дополнительном препроцессинге и требует только постоянную дополнительную память по отношению к оригинальному алгоритму относительно оригинального алгоритма Бойера-Мура. Она Он состоит в запоминании фактор сегмента текста, который соответствует суффикс паттерна шаблона во время последней попытки (и только тогда, когда хороший сдвиг хорошего суффикса сдвиг был выполнен).
Эта методика представляет два преимущества:
==Псевдокод==
==Асимптотики==
