418
правок
Изменения
→Предварительные вычисления
* <tex>x[\mathrm{H_{max}}(k)] \neq x[\mathrm{H_{max}}(k)-k]</tex>.
}}
{{Определение
|definition=
Обозначим за <tex>\mathrm{nhd0}(i)</tex> количество насыщенных позиций строго меньших <tex>i</tex>.
}}
Теперь мы можем определить два функции <tex>shift</tex> и <tex>next</tex>:
* <tex>\mathrm{shift}(i)=\mathrm{K_{min}}(h[i])</tex> и <tex>\mathrm{next}(i)=\mathrm{nhd0}(h[i]-\mathrm{K_{min}}(h[i]))</tex> для всех <tex>i : i < nd</tex>;
* <tex>\mathrm{shift}(i)=\mathrm{R_{min}}(h[i])</tex> и <tex>\mathrm{next}(i)=\mathrm{nhd0}(m-\mathrm{R_{min}}(h[i]))</tex> для всех <tex>i : nd \leqslant i < m</tex>;
* <tex>\mathrm{shift}(m)=\mathrm{R_{min}}(0)</tex> и <tex>\mathrm{next}(m)=\mathrm{nhd0}(m-\mathrm{R_{min}}(h[m-1]))</tex>.
Таким образом, при возникновении несовпадения между <tex>x[h[r]]</tex> и <tex>y[j+h[r]]</tex> окно сравнения должно быть сдвинуто на <tex>shift(r)</tex> и сравнения могут быть продолжены с позиции h[next[r]] шаблона <tex>x</tex>.
==Псевдокод==
