Изменения

Перейти к: навигация, поиск

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

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

Навигация