251
правка
Изменения
→Асимптотика
==Асимптотика==
{{Утверждение|statement= Фаза препроцессинга требует <tex>O(m + \sigma)</tex> времени и памяти, где <tex>\sigma</tex> {{---}} размер алфавита, <tex>m</tex> {{---}} длина шаблона.
|proof= Стадия препроцессинга совпадает со стадией препроцессинга в [[Алгоритм Бойера-Мура|алгоритме Бойера-Мура]], поэтому рассмотрим только стадию поиска.}}
{{Утверждение|statement= Фаза поиска требует <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} длина строки, в которой выполняется поиск.
