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