418
правок
Изменения
Нет описания правки
Алгоритм, разработанный Ливио Колусси, профессором итальянского университета Padova, и опубликованный им в 1991 году, является продолжением работы над оптимизацией [[Алгоритм Кнута-Морриса-Пратта|алгоритма Кнута-Морриса-Пратта]]. Предназначен для поиска одной подстроки в нескольких текстах.
==Алгоритм==
Алгоритм сравнивает символы шаблона <tex>x</tex> один за другим с символами исходной строки <tex>y</tex>. Для сдвигов шаблона относительно исходной строки применяются вспомогательные функции, описанные ниже.
Обозначим за <tex>\mathrm{Kmp}</tex> {{---}} [[Префикс-функция|префикс-функцию]], но при этом она определена для <tex>x[0] \dots x[m-1]</tex> и имеет значение <tex>-1</tex> по умолчанию.
Отметим, что нумерация символов строк и элементов массива у нас начинается с <tex>0</tex>.
{{Определение
Такая стратегия предоставляет, как минимум, 2 преимущества:
* когда несовпадение появляется во время первой фазы, после соответствующего сдвига уже нет необходимости делать проверки в насыщенных позициях, которые были проверены на предыдущем шаге.
* когда несовпадение появляется во время второй фазы, это означает, что суффикс шаблона совпал с периодом (''factor'') подстрокой исходной строки, <tex>y</tex> и после соответствующего сдвига префикс шаблона будет все ещё совпадать с периодом текстаэтой подстрокой, поэтому нет необходимости в повторной проверке.
{{Определение
|definition=
Обозначим за <tex>\mathrm{K_{min}}(i) = \min\{k : \ x[0 \dots i-1-k]=x[d \dots i-1]\ and\ x[i-k] \neq x[i]\}</tex>. Функция <tex>\mathrm{K_{min}}</tex> определена для всех позиций <tex>i</tex>, у которых <tex>\mathrm{Kmp}(i) \neq -1</tex>.
}}
Очевидно, что для <tex>0 < i < m</tex> позиция <tex>i</tex>:
* насыщенная, если <tex>\mathrm{K_{min}}(i-1) \neq 0</tex>,* ненасыщенная, иначев остальных случаях.
Обозначим за <tex>nd+1</tex> количество насыщенных позиций в шаблоне <tex>x</tex>.
{{Определение
|definition=
Обозначим за <tex>\mathrm{R_{min}}(i)</tex> наименьший период <tex>r</tex> шаблона <tex>x</tex> большего, чем <tex>i</tex>. Функция <tex>\mathrm{R_{min}}</tex> определена для всех позиций <tex>i</tex>, у которых <tex>\mathrm{Kmp}(i) = -1</tex>.
}}
}}
Теперь рассмотрим 2 случаях, возможных при очередной попытке сравнения шаблона с подстрокой из текста. Допустим, что шаблон <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>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>.
