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

Алгоритм Бойера-Мура за линейное время(Турбо-алгоритм) является улучшением алгоритма Бойера-Мура. Алгоритм, разработанный группой учёных во главе с М.Крочемором предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае.

Алгоритм

Турбо-алгоритм Бойера-Мура не нуждается в дополнительном препроцессинге и требует только постоянную дополнительную память по отношению к оригинальному алгоритму Бойера-Мура. Она состоит в запоминании фактор текста, который соответствует суффикс паттерна во время последней попытки (и только тогда, когда хороший суффикса сдвиг был выполнен).

Эта методика представляет два преимущества:

      можно перепрыгнуть через этот фактор;
      она может позволить выполнять турбо-сдвиг.

См. также

• Алгоритм Бойера-Мура
• Алгоритм Райта
• Алгоритм Кнута-Морриса-Пратта
• Алгоритм Апостолико-Крочемора

Ссылки

• Википедия — Алгоритм Бойера-Мура
• Wikipedia — Boyer–Moore string search algorithm
• Turbo Boyer-Moore algorithm