Изменения

{{Утверждение|statement= * Фаза препроцессинга требует <tex>O(m + \sigma)</tex> времени и памяти, где <tex>\sigma</tex> {{---}} размер алфавита, <tex>m</tex> {{---}} длина шаблона. * |proof= Стадия препроцессинга совпадает со стадией препроцессинга в [[Алгоритм Бойера-Мура|алгоритме Бойера-Мура]], поэтому рассмотрим только стадию поиска.}}{{Утверждение|statement= Фаза поиска требует <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} длина строки, в которой выполняется поиск.* }}{{Утверждение|statement= В худшем случае поиск требует <tex>O(2n)</tex> сравнений.|proof= Стадия препроцессинга совпадает со стадией препроцессинга в [[Алгоритм Бойера-Мура|алгоритме Бойера-Мура]], поэтому рассмотрим только стадию поиска. Разобьём поиск на стадии. Каждая стадия делится на две операции: сканирование и сдвиг. На этапе <tex>k</tex> мы назовём <tex>suf_k</tex> длину суффикса шаблона, что совпадает с текстом. Этому предшествует символ, который не совпадает с соответствующим символом в тексте (в случае когда <tex>suf_k</tex> не соответствует длине шаблона). Мы также назовём <tex>shift_k</tex> длину сдвига, сделанного на этапе <tex>k</tex>.