418
правок
Изменения
Нет описания правки
Алгоритм, разработанный Ливио Колусси, профессором итальянского университета Padova, и опубликованный им в 1991 году, является продолжением работы над оптимизацией [[Алгоритм Кнута-Морриса-Пратта|алгоритма Кнута-Морриса-Пратта]]. Предназначен для поиска одной подстроки в нескольких текстаходном тексте.
==Алгоритм==
* <tex>\mathrm{shift}(m)=\mathrm{R_{min}}(0)</tex> и <tex>\mathrm{next}(m)=\mathrm{nhd0}(m-\mathrm{R_{min}}(h[m-1]))</tex>.
Таким образом, при возникновении несовпадения между <tex>x[h[r]]</tex> и <tex>y[j+h[r]]</tex> окно сравнения должно быть сдвинуто на <tex>\mathrm{shift}(r)</tex> и сравнения могут быть продолжены с позиции <tex>h[\mathrm{next[}(r)]] </tex> шаблона <tex>x</tex>.
==Псевдокод==
Функция для построения массива <tex>\mathrm{H_{max}}</tex>.
'''Наивный вариант'''
'''int'''[] buildHmax('''char'''[] x, '''int''' m):
Функция для построения массива <tex>\mathrm{next}</tex>.
'''int'''[] buildNext('''int'''[] kmin, '''int'''[] rmin, '''int'''[] h, '''int''' nd, '''int''' m)
<font color="green">// Вычисление массива <tex>\mathrm{nhd0}</tex></font>
'''int''' nhd0[m]
'''int''' s = 0
'''for''' i = 0 .. m - 1
++s
<font color="green">// Вычисление массива <tex>\mathrm{next}</tex></font> '''int'''[] next = new int[m + 1]
'''for''' i = 0 .. nd
next[i] = nhd0[h[i] - kmin[h[i]]]
next[m] = nhd0[m - rmin[h[m - 1]]]
'''return''' next
Основная функция алгоритма Колусси.
'''void''' COLUSSI('''char'''[] x, '''char'''[] y)
'''int''' n = length(y)
'''int''' m = length(x)
<font color="green">// Предварительные вычисления</font>
'''int'''[] hmax = buildHmax(x, m)
'''int'''[] kmin = buildKmin(hmax, m)
'''int'''[] rmin = buildRmin(hmax, kmin, m)
<font color="green">// Построение массива <tex>h</tex></font>
'''int''' h[m]
'''int''' s = -1
'''int''' r = m
'''for''' i = 0 .. m - 1
'''if''' kmin[i] == 0
h[--r] = i
'''else'''
h[++s] = i
'''int''' nd = s
'''int'''[] shift = buildShift(kmin, rmin, h, nd, m)
'''int'''[] next = buildNext(kmin, rmin, h, nd, m)
<font color="green">// Поиск подстроки</font>
'''int''' i = 0
'''int''' j = 0
'''int''' last = -1
'''while''' j <= n - m
'''while''' i < m '''and''' last < j + h[i] '''and''' x[h[i]] == y[j + h[i]]
++i
'''if''' i >= m '''or''' last >= j + h[i]
OUTPUT(j)
i = m
'''if''' i > nd
last = j + m - 1
j += shift[i]
i = next[i]
==Асимптотики==
