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