Турбо-алгоритм Бойера-Мура — различия между версиями
Zemskovk (обсуждение | вклад) |
Zemskovk (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
'''Алгоритм Бойера-Мура за линейное время(Турбо-алгоритм)''' является улучшением [[Алгоритм Бойера-Мура|алгоритма Бойера-Мура]]. Алгоритм, разработанный группой учёных во главе с М.Крочемором предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае. | '''Алгоритм Бойера-Мура за линейное время(Турбо-алгоритм)''' является улучшением [[Алгоритм Бойера-Мура|алгоритма Бойера-Мура]]. Алгоритм, разработанный группой учёных во главе с М.Крочемором предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае. | ||
==Алгоритм== | ==Алгоритм== | ||
| − | Турбо-алгоритм Бойера-Мура не нуждается в дополнительном препроцессинге и требует только постоянную дополнительную память | + | Турбо-алгоритм Бойера-Мура не нуждается в дополнительном препроцессинге и требует только постоянную дополнительную память относительно оригинального алгоритма Бойера-Мура. Он состоит в запоминании сегмента текста, который соответствует суффикс шаблона во время последней попытки (и только тогда, когда сдвиг хорошего суффикса был выполнен). |
| − | |||
Эта методика представляет два преимущества: | Эта методика представляет два преимущества: | ||
| − | + | # можно перепрыгнуть через этот сегмент; | |
| − | + | # она может позволить выполнение 'турбо-сдвига'. | |
| − | |||
==Псевдокод== | ==Псевдокод== | ||
==Асимптотики== | ==Асимптотики== | ||
Версия 23:02, 30 марта 2016
Алгоритм Бойера-Мура за линейное время(Турбо-алгоритм) является улучшением алгоритма Бойера-Мура. Алгоритм, разработанный группой учёных во главе с М.Крочемором предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае.
Содержание
Алгоритм
Турбо-алгоритм Бойера-Мура не нуждается в дополнительном препроцессинге и требует только постоянную дополнительную память относительно оригинального алгоритма Бойера-Мура. Он состоит в запоминании сегмента текста, который соответствует суффикс шаблона во время последней попытки (и только тогда, когда сдвиг хорошего суффикса был выполнен). Эта методика представляет два преимущества:
- можно перепрыгнуть через этот сегмент;
- она может позволить выполнение 'турбо-сдвига'.
