418
правок
Изменения
Нет описания правки
Тогда для всех <tex>i</tex> таких, что <tex>0 \leqslant i < m</tex> выполняется <tex>bmGs[i+1]=\min\{s > 0 : Cs(i, s)\ and\ Co(i, s)\}</tex>. А значение <tex>bmGs[0]</tex> определим, как длину периода шаблона <tex>x</tex>.
Для вычисления bmGs будем использовать массив функцию <tex>suffsuffixLength</tex>, определенный определенную так:для всех <tex>i</tex> таких, что <tex>1 \leqslant i < m</tex> выполняется <tex>suffsuffixLength[i]=\max\{k : x[i-k+1 .. i]=x[m-k .. m-1]\}</tex>
Сдвиги плохих символов будем хранить в массиве <tex>bmBc</tex> размером <tex>\sigma</tex>.
'''int'''[] preBmBc('''char'''[] x, '''int''' m):
'''int''' table[ASIZE];
<font color=green>// Заполняем значением по умолчанию, равным длине шаблона</font>
'''for''' i = 0 .. ASIZE - 1
table[i] = m
<font color=green>// Вычисление функции по определению</font>
'''for''' i = 0 .. m - 2
table[x[i]] = m - 1 - i
'''int''' lastPrefixPosition = m
'''for''' i = m - 1 .. 0
<font color=green>// Если подстрока x[i+1..m-1] является префиксом, то запомним её начало</font>
'''if''' isPrefix(x, m, i + 1)
lastPrefixPosition = i + 1
table[m - 1 - i] = lastPrefixPosition - i + m - 1
<font color=green>// Вычисление функции по определению</font>
'''for''' i = 0 .. i < m - 2
'''int''' slen = suffixLength(x, m, i)
