177
правок
Изменения
→Псевдокод
Функция для вычисления таблицы сдвигов плохих символов. Она будет равна длине шаблона для всех символов, которые не встречаются в шаблоне, и порядковому номеру с конца для остальных (кроме последнего, для него тоже берется длина шаблона). Вычисляется прямо по определению за <tex>O(m+\sigma)</tex>
'''int'''[] preBmBc('''char'''[m] x, '''int''' m):
'''int''' table[ASIZE]
<font color=green>// Заполняем значением по умолчанию, равным длине шаблона</font>
Функция, проверяющая, что подстрока <tex>x[p \dots m - 1]</tex> является префиксом шаблона <tex>x</tex>. Требует <tex>O(m - p)</tex> времени.
'''boolean''' isPrefix('''char'''[m] x, '''int''' m, '''int''' p):
'''int''' j = 0
'''for''' i = p .. m - 1
Функция, возвращающая для позиции <tex>p</tex> длину максимальной подстроки, которая является суффиксом шаблона <tex>x</tex>. Требует <tex>O(m - p)</tex> времени.
'''int''' suffixLength('''char'''[m] x, '''int''' m, '''int''' p):
'''int''' len = 0
'''int''' i = p
Функция для вычисления сдвигов хороших суффиксов. Требует <tex>O(m)</tex> времени, несмотря на циклы в вызываемых функциях, из-за того, что каждый внутренний цикл в худшем случае будет выполняться на каждой позиции <tex>i</tex> не больше, чем <tex>i</tex> раз. Получается натуральный ряд, сумма <tex>m</tex> первых членов которого <tex dpi="150">\frac{m \cdot (m - 1)}{2}</tex>. Следовательно, получается оценка по времени <tex>O(m^2)</tex>.
'''int'''[] preBmGs('''char'''[m] x, '''int''' m):
'''int''' table[m]
'''int''' lastPrefixPosition = m
