Турбо-алгоритм Бойера-Мура
Алгоритм Бойера-Мура за линейное время(Турбо-алгоритм) является улучшением алгоритма Бойера-Мура. Алгоритм, разработанный группой учёных во главе с М.Крочемором предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае.
Содержание
Алгоритм
Турбо-алгоритм Бойера-Мура не нуждается в дополнительном препроцессинге и требует только постоянную дополнительную память относительно оригинального алгоритма Бойера-Мура. Он состоит в запоминании сегмента текста, который соответствует суффикс шаблона во время последней попытки (и только тогда, когда сдвиг хорошего суффикса был выполнен). Эта методика представляет два преимущества:
- можно перепрыгнуть через этот сегмент;
- она может позволить выполнение 'турбо-сдвига'.
Турбо - сдвиг может произойти, если мы обнаружим, что суффикс образца, который сходится с текстом, короче, чем тот, который был запомнен ранее.
Пусть - запомненный сегмент, а - cуффикс, совпавший во время текущей попытки, такой что - суффикс . Тогда - суффикс , два символа и встречаются на расстоянии в тексте, и суффикс длины имеет период длины , а значит не может перекрыть оба появления символов и в тексте. Наименьший возможный сдвиг имеет длину ( его мы и называем турбо - сдвигом ).
Применение турбо-сдвига в случае
При , если сдвиг плохого символа больше, то совершаемый сдвиг будет больше либо равен . В этом случае символы и различны, так как мы предположили, что предыдущий сдвиг был сдвигом хорошего суффикса. Тогда сдвиг больший, чем турбо-сдвиг, но меньший совместит и с одним и тем же символом . Значит, если сдвиг плохого символа больше, то мы можем применить сдвиг больший, либо равный . Нельзя совместить символы с одним и тем же символом v.
