Изменения
Нет описания правки
Введем обозначение: пусть <tex>t[i]</tex> {{---}} длина наибольшего бордера для <tex>x[0 .. i - 1]</tex> за которым следует символ <tex>c \neq x[i]</tex> и <tex>-1</tex> если нет такого помеченного бордера, где <tex>0 < i \le m</tex> (<tex>t[0] = -1</tex>). Затем после сдвига сравнение можно продолжить между символами <tex>x[t[i]]</tex> и <tex>y[i + j]</tex> не потеряв никакого вхождения <tex>x</tex> в <tex>y</tex> и избежав отступа по тексту (смотри рис. 1).
===Псевдокод===
empty
Пусть теперь <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>(i, j, k)</tex> где:
* шаблон сравнивается с <tex>y[j, \ldots , j + m - 1]</tex>
* <tex>0 \le k \le l</tex> и <tex>x[0, \ldots, k - 1] {{=}} y[j, \ldots , j + k - 1]</tex>
* <tex>l \le i < m</tex> и <tex>x[l, \ldots, i - 1] {{=}} y[j + l, \ldots , i + j - 1]</tex>
Вначале инициализируем эту тройку <tex>(l, 0, 0)</tex>.
Теперь опишем, как по уже вычисленной тройке <tex>(i, j, k)</tex> перейти к следующей.
Возможны три случая в зависимости от значения <tex>i</tex>:
