251
правка
Изменения
→Асимптотика
}}
{{Утверждение|statement= В худшем случае поиск требует <tex>O(2n)</tex> сравнений.
|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>. Тогда три типа сдвигов будут:
