Изменения

Этап предподсчета, а именно вычисление массива <tex>t</tex> и переменной <tex>l</tex> занимает <math>O(m)</math> времени и константное количество памяти. Этап поиска занимает <math>O(n)</math> времени, более того, алгоритм в худшем случае выполнит <tex>\fracdfrac{3}{2} n</tex> сравнений.