418
правок
Изменения
Нет описания правки
Теперь рассмотрим 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>k : 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>.
[[Файл:colussi-algorithm-1.png|450px|thumb|center|Насыщенная позиция.]]
=== Второй случай ===
Кроме того равенство <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>.
[[Файл:colussi-algorithm-2.png|450px|thumb|center|Ненасыщенная позиция.]]
=== Предварительные вычисления ===
Функция для построения массива <tex>\mathrm{K_{min}}</tex>.
'''int'''[] buildKmin('''int'''[] hmax, '''int''' m):
'''int''' kmin[m]
'''for''' i = m .. 1
Функция для построения массива <tex>\mathrm{R_{min}}</tex>.
'''int'''[] buildRmin('''int'''[] hmax, '''int'''[] kmin, '''int''' m):
'''int''' rmin[m]
'''int''' r = 0
Функция для построение массива <tex>\mathrm{shift}</tex>.
'''int'''[] buildShift('''int'''[] kmin, '''int'''[] rmin, '''int'''[] h, '''int''' nd, '''int''' m):
'''int''' shift[m + 1]
'''for''' i = 0 .. nd
Функция для построения массива <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]
Основная функция алгоритма Колусси.
'''void''' COLUSSI('''char'''[] x, '''char'''[] y):
'''int''' n = length(y)
'''int''' m = length(x)
