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