418
правок
Изменения
м
Вторая фаза состоит в сравнении Во втором случае будут производиться сравнения в оставшихся позициях справа налево. Такие позиции будем называть '''ненасыщенными''' (''holes'').
Нет описания правки
Отметим, что нумерация символов строк и элементов массива у нас начинается с <tex>0</tex>.
Множество всех позиций шаблона разделим на два (дизъюнктных) непересекающихся множества. Тогда каждая попытка сравнения шаблона с исходной строкой после очередного сдвига состоит из двух фазслучаев.
{{Определение
|definition=
В первой фазе первом случае сравнения выполняются слева направо с символами текста, выровненными с шаблоном в позиции, для которой значение функции <tex>\mathrm{Kmp}(i)</tex> строго больше <tex>-1</tex>. Такие позиции будем называть '''насыщенными''' (''noholes'').
}}
{{Определение
|definition=
}}
Такая стратегия предоставляет, как минимум, 2 преимущества:
* когда несовпадение появляется во время первой фазыпервого случая, после соответствующего сдвига уже нет необходимости делать проверки в насыщенных позициях, которые были проверены на предыдущем шаге.* когда несовпадение появляется во время второй фазывторого случая, это означает, что суффикс шаблона совпал с подстрокой исходной строки <tex>y</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>.
return rmin
Функция для построение массива <tex>\mathrm{Shiftshift}</tex>.
'''int'''[] buildShift('''int'''[] kmin, '''int'''[] rmin, '''int'''[] h, '''int''' nd, '''int''' m)
'''int''' shift[m + 1]
'''return''' shift
Функция для построения массива <tex>\mathrm{Nextnext}</tex>. '''int'''[] buildNext('''int'''[] kmin, '''int'''[] rmin, '''int'''[] h, '''int''' nd, '''int''' m) // Вычисление массива nhd0 '''int''' nhd0[m] '''int''' s = 0 '''for''' i = 0 .. m - 1 nhd0[i] = s if kmin[i] > 0 ++s // Вычисление массива next '''int'''[] next = new int[m + 1] '''for''' i = 0 .. nd next[i] = nhd0[h[i] - kmin[h[i]]] '''for''' i = nd + 1 .. m - 1 next[i] = nhd0[m - rmin[h[i]]] next[m] = nhd0[m - rmin[h[m - 1]]] '''return''' next
==Асимптотики==
