251
правка
Изменения
→Алгоритм
# можно перепрыгнуть через этот сегмент;
# она может позволить выполнение 'турбо-сдвига'.
Турбо - сдвиг может произойти, если мы обнаружим, что суффикс образца, который сходится с текстом, короче, чем тот, который был запомнен ранее.
Пусть <tex>u</tex> - — запомненный сегмент, а <tex>v</tex> - — cуффикс, совпавший во время текущей попытки, такой что <tex>uzv</tex> - — суффикс <tex>x</tex>. Тогда <tex>av</tex> - — суффикс <tex>x</tex>, два символа <tex>a</tex> и <tex>b</tex> встречаются на расстоянии <tex>p</tex> в тексте, и суффикс <tex>x</tex> длины <tex>|uzv|</tex> имеет период длины <tex>p</tex>, а значит не может перекрыть оба появления символов <tex>a</tex> и <tex>b</tex> в тексте. Наименьший возможный сдвиг имеет длину <tex>|u| - |v|</tex> ( его мы и называем турбо - сдвигом ).[[Файл:Tbm1.png|800px|center]]
===Применение турбо-сдвига в случае <tex>|v| < |u|</tex>===
[[Файл:Tbm2.png|800px|center]]
Нельзя совместить символы <tex>c \neq d</tex> с одним и тем же символом v.
==Псевдокод==
Стадия препроцессинга совпадает со стадией препроцессинга в [[Алгоритм Бойера-Мура|алгоритме Бойера-Мура]].
