251
правка
Изменения
→Асимптотика
|proof= Стадия препроцессинга совпадает со стадией препроцессинга в [[Алгоритм Бойера-Мура|алгоритме Бойера-Мура]], поэтому рассмотрим только стадию поиска.
Разобьём поиск на стадии. Каждая стадия делится надве операции: сканирование и сдвиг. На этапе <tex>k</tex> мы назовём <tex>suf_k</tex> длину суффикса шаблона, что совпадает с текстом. Этому предшествует символ, который несовпадает с соответствующим символом в тексте (в случае когда <tex>suf_k</tex> не соответствует длине шаблона). Мы такженазовём <tex>shift_k</tex> длину сдвига , сделанного на этапе <tex>k</tex>.
Рассмотрим три типа стадий в зависимости от характера сканирования и сдвига. Мы говорим, что сдвиг на стадии <tex>k</tex> короткий, если <tex>2shift_k < suf_k + 1</tex>. Тогда три типа сдвигов будут:
