1632
правки
Изменения
м
next[i] = nhd0[m - rmin[h[i]]]
rollbackEdits.php mass rollback
==Алгоритм==
Алгоритм сравнивает символы шаблона <tex>x</tex> один за другим с символами исходной строки <tex>y</tex>. Для сдвигов шаблона относительно исходной строки применяются вспомогательные функции, описанные ниже.
Пусть <tex>|y|=n</tex> и <tex>|x|=m</tex>.
Обозначим за <tex>\mathrm{Kmp}</tex> {{---}} [[Префикс-функция|префикс-функцию]], но при этом она определена для <tex>x[0] \dots x[m-1]</tex> и имеет значение <tex>-1</tex> по умолчанию.
Отметим, что нумерация символов строк и элементов массива у нас начинается с <tex>0</tex>.
Множество всех позиций шаблона разделим на два (дизъюнктных) непересекающихся множества. Тогда каждая попытка сравнения шаблона с исходной строкой после очередного сдвига состоит из двух случаев.
{{Определение
|definition=
В первом случае сравнения выполняются слева направо с символами текста, выровненными с шаблоном в позиции, для которой значение функции <tex>\mathrm{Kmp}(i)</tex> строго больше <tex>-1</tex>. Такие позиции будем называть '''насыщенными''' (англ. ''noholes'').
}}
{{Определение
|definition=
Во втором случае будут производиться сравнения в оставшихся позициях справа налево. Такие позиции будем называть '''ненасыщенными''' (англ. ''holes'').
}}
{{Определение
|definition=
Обозначим за <tex>\mathrm{first}(u)</tex> наименьший наименьшее число <tex>v</tex> такое, что <tex>u \leqslant h[v]</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</tex> и <tex>x[h[r]] \neq y[j+h[r]]</tex> для <tex>nd \leqslant r < m</tex>.
Пусть <tex>j' = j + \mathrm{R_{min}}(h[r])</tex> позиций вправо.
Тогда нет вхождений шаблона <tex>x</tex>, начиная с <tex>y[j \dots j']</tex> и <tex>x</tex> может быть сдвинут на <tex>\mathrm{R_{min}}(h[r])</tex>позиций вправо.
Кроме того равенство <tex>x[0 \dots m-1-\mathrm{R_{min}}(h[r])]=y[j' \dots j+m-1]</tex> означает, что сравнения могут продолжены с символов <tex>x[h[\mathrm{first}(m-1-\mathrm{R_{min}}(h[r]))]]</tex> и <tex>y[j'+h[\mathrm{first}(m-1-\mathrm{R_{min}}(h[r]))]]</tex>.
==Псевдокод==
Функция для построения массива <tex>\mathrm{H_{max}}</tex>.
'''Наивный вариант'''
'''int'''[] buildHmax('''char'''[] x, '''int''' m):
'''for''' k = 1 .. m
'''int''' i = k
'''while''' i < m and x[i] == x[i - k]
i++
hmax[k] = i
'''return ''' hmax
Явная реализация по определению, очевидно, работает за <tex>O(m^2)</tex> и требует <tex>O(m)</tex> памяти.
'''int''' k = 1
'''while''' k <= m
'''while''' i < m and x[i] == x[i - k] i++;
hmax[k] = i
'''int''' q = k + 1
q++
k = q
'''if ''' k == i + 1
i = k
'''return''' hmax
'''else'''
rmin[i] = 0
'''return ''' rmin
Функция для построение массива <tex>\mathrm{shift}</tex>.
next[i] = nhd0[h[i] - kmin[h[i]]]
'''for''' i = nd + 1 .. m - 1
next[m] = nhd0[m - rmin[h[m - 1]]]
'''return''' next
Основная функция алгоритма Колусси.
'''voidfunction''' COLUSSIcolussi('''char'''[] x, '''char'''[] y):
'''int''' n = length(y)
'''int''' m = length(x)
===Недостатки===
* Сложность реализации.
==Источникиинформации==
* 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]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Поиск подстроки в строке]]
[[Категория: Точный поиск]]
