177
правок
Изменения
→Псевдокод
==Псевдокод==
Константой <tex>|\Sigma|=\sigma=ASIZE</tex> обозначим размер нашего алфавита.
Функция для вычисления таблицы сдвигов плохих символов. Она будет равна длине шаблона для всех символов, которые не встречаются в шаблоне, и порядковому номеру с конца для остальных (кроме последнего, для него тоже берется длина шаблона). Вычисляется прямо по определению за <tex>O(m+\sigma)</tex>
'''int'''[] preBmBc('''char'''[m] x):
'''int''' table<tex>[ASIZE</tex> <tex>|\Sigma|</tex> <tex>]</tex>
<font color=green>// Заполняем значением по умолчанию, равным длине шаблона</font>
'''for''' i = 0 .. ASIZE <tex>|\Sigma|</tex> - 1
table[i] = m
<font color=green>// Вычисление функции по определению</font>
'''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 .. m - 2
'''int''' slen = suffixLength(x, m, i)
table[slen] = m - 1 - i + slen
'''return''' table
<font color=green>//Предварительные вычисления</font>
'''int''' bmBc[] = preBmBc(x, m) '''int''' bmGs[] = preBmGs(x, m)
<font color=green>//Поиск подстроки</font>
