Изменения

Отметим, что нумерация символов строк и элементов массива у нас начинается с <tex>0</tex>.

Обозначим за <tex>\mathrm{Kmp}</tex> {{---}} [[Префикс-функция|префикс-функцию]]. При , но при этом она должна быть определена для <tex>x[0] \dots x[m-1]</tex> и иметь имеет значение <tex>-1</tex> по умолчанию.

Для всех <tex>i</tex> таких, что <tex>0 \leqslant i \leqslant m-1</tex> выполняется:<br/>Обозначим за <tex>\mathrm{KminK_{min}}(i) = \begin{cases} d, & min\mbox{if } d > 0\ andk : \ x[0 \dots i-1-dk]=x[d \dots i-1]\ and\ x[i-dk] \neq x[i]\}</tex>. Функция <tex>\ 0, & \mboxmathrm{K_{otherwisemin}}</tex> для всех позиций <tex>i</tex>, у которых <tex>Kmp(i) \end{cases}neq -1</tex>.

Массив <tex>h</tex> содержит первые первыми элементами <tex>nd+1</tex> насыщенных позиций в возрастающем порядке и затем <tex>m-nd-1</tex> ненасыщенных в убывающем порядке, т.е.

Обозначим за <tex>\mathrm{RminFirst}(iu)</tex> наименьший период число <tex>v</tex> такое, что <tex>u \leqslant h[v]</tex>.}} Допустим, что шаблон <tex>x</tex> выровнен с <tex>y[j \dots j+m-1]</tex>.  == Первая фаза ==Рассмотрим случай, когда <tex>x[h[k]]=y[j+h[k]]</tex> для <tex>0 \leqslant k < r < nd</tex> и <tex>x[h[r]] \neq y[j+h[r]]</tex>. Пусть <tex>j' = j + \mathrm{Kmin}(h[r])</tex>.  Тогда нет вхождений шаблона <tex>x</tex>, начиная с <tex>y[j \dots j']</tex> и <tex>x</tex> может быть сдвинут на <tex>\mathrm{K_{min}}(h[r])</tex> позиций вправо. Кроме того <tex>x[h[k]]=y[j’+h[k]]</tex> для <tex>0 \leqslant k < \mathrm{first}(h[r]-\mathrm{K_{min}}(h[r]))</tex> означает, что сравнения могут продолжены с <tex>x[h[\mathrm{first}(h[r] - \mathrm{K_{min}}(h[r]))]]</tex> и <tex>y[j'+h[\mathrm{first}(h[r]-\mathrm{K_{min}}(h[r]))]]</tex>. == Вторая фаза ==Теперь рассмотрим ситуацию, когда <tex>x[h[k]]=y[j+h[k]]</tex> для <tex>0 \leqslant k < r</tex> и <tex>x[h[r]] \neq y[j+h[r]]</tex> для <tex>nd \leqslant r < m</tex>.  Пусть <tex>j' = j + \mathrm{R_{min}}(h[r])</tex> позиций вправо.  Тогда нет вхождений шаблона <tex>x</tex> большего, чем начиная с <tex>y[j \dots j']</tex> и <tex>x</tex> может быть сдвинут на <tex>\mathrm{R_{min}}(h[r])</tex>. Кроме того <tex>x[0 \dots m-1-\mathrm{R_{min}}(h[r])]=y[j' \dots j+m-1]</tex> означает, что сравнения могут продолжены с <tex>ix[h[\mathrm{first}(m-1-\mathrm{R_{min}}(h[r]))]]</tex> и <tex>y[j'+h[\mathrm{first}(m-1-\mathrm{R_{min}}(h[r]))]]</tex>. == Предварительные вычисления ==Для вычисления значений <tex>\mathrm{K_{min}}</tex> будем использовать вспомогательную функцию <tex>\mathrm{H_{max}}</tex>.{{Определение|definition=Обозначим за <tex>\mathrm{H_{max}}</tex> функцию, для которой выполняется:* <tex>x[k \dots \mathrm{H_{max}}(k)-1]=x[0 \dots \mathrm{H_{max}}(k)-k-1]</tex>,* <tex>x[\mathrm{H_{max}}(k)] \neq x[\mathrm{H_{max}}(k)-k]</tex>.