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>. Тогда эти три типа будут:
# Шаг с длинным сдвигом, без последующего шага с прыжком.
# Шаг с коротким сдвигом, без последующего шага с прыжком.
Идея доказательства состоит в [[Амортизационный_анализ|амортизации ]] стоимости сравнения со сдвигами. Определим стоимость шага <tex>cost_k</tex> следующим образом:
* Если шаг <tex>k</tex> имеет тип (1), <tex>cost_k = 1</tex>.
* Если шаг <tex>k</tex> имеет тип (2) или (3), стоимость <tex>cost_k = suf_k + 1</tex>.
