Изменения

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

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

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

Навигация