418
правок
Изменения
→Алгоритм
Отметим, что нумерация символов строк и элементов массива у нас начинается с <tex>0</tex>.
Обозначим за <tex>\mathrm{Kmp}</tex> [[Префикс-функция|префикс-функцию]]. При этом она должна быть определена для <tex>x[0] \dots x[m-1]</tex> и иметь значение <tex>-1</tex> по умолчанию. Множество всех позиций шаблона разделим на два непересекающихся множества. Тогда каждая попытка сравнения шаблона с исходной строкой состоит из двух фаз. {{Определение|definition=В первой фазе сравнения выполняются слева направо с символами текста, выровненными с шаблоном в позиции, для которой значение функции <tex>\mathrm{Kmp}(i)</tex> строго больше <tex>-1</tex>. Такие позиции будем называть '''насыщенными''' (''noholes'').}} {{Определение|definition=Вторая фаза состоит в сравнении в оставшихся позициях справа налево. Такие позиции будем называть '''ненасыщенными''' (''holes'').}} Такая стратегия предоставляет, как минимум, 2 преимущества:* когда несовпадение появляется во время первой фазы, после соответствующего сдвига уже нет необходимости делать проверки в насыщенных позициях, которые были проверены на предыдущем шаге.* когда несовпадение появляется во время второй фазы, это означает, что суффикс шаблона совпал с периодом (''factor'') строки, после соответствующего сдвига префикс шаблона будет все ещё совпадать с периодом текста, поэтому нет необходимости в повторной проверке.
{{Определение
}}
Если <tex>\mathrm{Kmin}(i) \neq 0</tex>, то периодичность шаблона <tex>x</tex> заканчивается в позиции <tex>i</tex>.
Очевидно, что для <tex>0 < i < m</tex> позиция <tex>i</tex>:
* насыщенная, если <tex>\mathrm{Kmin}(i-1) \neq 0</tex>
* ненасыщенная, иначе
Обозначим за <tex>nd+1</tex> количество насыщенных позиций в шаблоне <tex>x</tex>.
Массив <tex>h</tex> содержит первые <tex>nd+1</tex> насыщенных позиций в возрастающем порядке и затем <tex>m-nd-1</tex> ненасыщенных в убывающем порядке, т.е.
* для всех <tex>0 \leqslant i \leqslant nd</tex> <tex>h[i]</tex> насыщенная позиция и <tex>h[i] < h[i+1]</tex> для <tex>0 \leqslant i < nd</tex>.
* для всех <tex>nd < i < m</tex> <tex>h[i]</tex> ненасыщенная и <tex>h[i] > h[i+1]</tex> для <tex>nd < i < m-1</tex>.
{{Определение
|definition=
Обозначим за <tex>\mathrm{Rmin}(i)</tex> наименьший период шаблона <tex>x</tex> большего, чем <tex>i</tex>.
}}
{{Определение
|definition=
Обозначим за <tex>\mathrm{Rmin}(i)</tex> наименьший период шаблона <tex>x</tex> большего, чем <tex>i</tex>.
}}
==Псевдокод==
