Изменения

Пусть теперь <tex>l {{=}} 0</tex>, если <tex>x = c ^ m</tex> и <tex>c \in \Sigma</tex>, иначе <tex>l</tex> равно позиции первого элемента, который не равен <tex>x[0]</tex> (<tex>x {{=}} (a ^ l)bu</tex>, где <tex>a</tex> и <tex>b \in \Sigma</tex>, а <tex>u \in \Sigma^*</tex> и <tex>a \neq b</tex>). На каждой итерации алгоритма мы выполняем сравнения с шаблоном в следующем порядке: <tex>l, l + 1, \ldots , m - 2, m - 1, 0, 1, \ldots , l - 1</tex>.

#: Иначелибо <tex>k < l</tex> и <tex>x[k] \ne y[l + k]</tex>, либо <tex>k = l</tex>. Если <tex>k = l</tex>, то вхождение x в y найдено. В обоих случаях следующая тройка вычисляется как в случае <tex>l < i < m </tex>. ==Асимптотика алгоритма==Стадия предподсчета, а именно вычисление массива <tex>t</tex> и переменной <tex>l</tex> занимает <math>O(m)</math> времени и константное количество памяти. Этап поиска занимает <math>O(n)</math> времени более того алгоритм в худшем случае выполнит <tex>\frac{3}{2} n</tex> сравнений.