418
правок
Изменения
Нет описания правки
Отметим, что нумерация символов строк и элементов массива у нас начинается с <tex>0</tex>.
{{Определение
|definition=Обозначим за Для всех <tex>\mathrm{Kmin}(i)=i - \mathrm{Kmp}(i)</tex> функциютаких, возвращающую количество прыжков для позиций что <tex>0 \leqslant i</tex>, которые являются полными.}} {{Определение|definition=Обозначим за <tex>\mathrm{Rmin}(i)leqslant m-1</tex> функцию, возвращающую наименьший из периодов шаблона, которые больше позиции <tex>iвыполняется:<br/tex>, для позиций, которые являются пустыми.}} {{Определение|definition=Функция сдвига <tex>\mathrm{ShiftKmin}(i) = \begin{cases} \mathrm{Rmin}(i)d, & \mbox{if } d > 0\ and\ x[0 \mathrm{Kmp}(dots i) -1-d]= x[d \dots i-1]\ and\ x[i-d] \neq x[i]\\ \mathrm{Kmin}(i)0, & \mbox{otherwise}
\end{cases}</tex>
}}
==Псевдокод==
'''Наивный вариант'''
'''int'''[] buildHmax('''char'''[] x, '''int''' m):
На каждой итерации цикла увеличивается либо переменная <tex>i</tex>, либо <tex>k</tex> (или переменная <tex>q</tex>, которая используется в конечном счете для обновления <tex>k</tex>). Поскольку <tex>i = 1</tex> и <tex>k = 1</tex> в начале и <tex>i < k = m + 1</tex> в конце алгоритма, количество итераций алгоритма не превосходит <tex>2 \cdot m</tex>. Следовательно функция требует <tex>O(m)</tex> времени и памяти.
Функция для построения массива <tex>\mathrm{Kmin}</tex>.
'''int'''[] buildKmin('''int'''[] hmax, '''int''' m)
'''int''' kmin[m]
'''return''' kmin
Функция для построения массива <tex>\mathrm{Rmin}</tex>.
'''int'''[] buildRmin('''int'''[] hmax, '''int'''[] kmin, '''int''' m)
'''int''' rmin[m]
'''for''' i = m - 1 .. 0
'''if''' hmax[i + 1] == m
<font color="green">// <tex>r</tex> {{---}} первое число большее, чем <tex>i</tex> и такое, что шаблон имеет период <tex>r</tex></font>
r = i + 1
'''if''' kmin[i] == 0
rmin[i] = 0
return rmin
Функция для построение массива <tex>\mathrm{Shift}</tex>.
'''int'''[] buildShift('''int'''[] kmin, '''int'''[] rmin, '''int'''[] h, '''int''' nd, '''int''' m)
'''int''' shift[m + 1]
'''for''' i = 0 .. nd
shift[i] = kmin[h[i]]
'''for''' i = nd + 1 .. m - 1
shift[i] = rmin[h[i]]
shift[m] = rmin[0]
'''return''' shift
Функция для построения массива <tex>\mathrm{Next}</tex>.
==Асимптотики==
==Сравнение с другими алгоритмами==
===Достоинства===
* Поиск выполняется за <tex>O(n)</tex> в отличие от [[Алгоритм Кнута-Морриса-Пратта|алгоритма Кнута-Морриса-Пратта]], поиск в котором занимается <tex>O(n+m)</tex>, что помогает уменьшить константу при <tex>m~n</tex>.
* Фаза предобработки выполняется за <tex>O(m)</tex> в отличие от [[Алгоритм Бойера-Мура|алгоритма Бойера-Мура]], где в наилучшем случае можно получить время <tex>O(n+|\Sigma|)</tex>, что плохо при больших алфавитах.
===Недостатки===
* Сложность реализации.==СсылкиИсточники==* COLUSSI L., 1991, Correctness and efficiency of the pattern matching algorithms, Information and Computation 95(2):225-251.
* [http://www-igm.univ-mlv.fr/~lecroq/string/node10.html Colussi algorithm]
* [http://alg.csie.ncnu.edu.tw/course/StringMatching/Colussi.ppt Colussi.ppt]
