251
правка
Изменения
Нет описания правки
# можно перепрыгнуть через этот сегмент;
# она может позволить выполнение 'турбо-сдвига'.
Турбо - сдвиг может произойти, если мы обнаружим, что суффикс образца, который сходится с текстом, короче, чем тот, который был запомнен ранее.
Пусть <tex>u</tex> - запомненный сегмент, а <tex>v</tex> - cуффикс, совпавший во время текущей попытки, такой что <tex>uzv</tex> - суффикс <tex>x</tex>. Тогда <tex>av</tex> - суффикс <tex>x</tex>, два символа <tex>а</tex> и <tex>b</tex> встречаются на расстоянии p в тексте, и суффикс x длины |uzv| имеет период длины p, а значит не может перекрыть оба появления символов а и b в тексте. Наименьший возможный сдвиг имеет длину |u| - |v| ( его мы и называем турбо - сдвигом ).
==Псевдокод==
==Асимптотики==
