418
правок
Изменения
→Псевдокод
Функция для вычисления таблицы сдвигов плохих символов. Она будет равна длине шаблона для всех символов, которые не встречаются в шаблоне, и порядковому номеру с конца для остальных (кроме последнего, для него тоже берется длина шаблона). Вычисляется прямо по определению за <tex>O(m+\sigma)</tex>
'''int'''[] preBmBc('''stringchar''' [] x, '''int''' m): '''int''' bmBctable[ASIZE] <font color=green>// Значение по умолчанию = m</font>; '''for''' i = 0 .. ASIZE-1 bmBctable[i] = m
'''for''' i = 0 .. m - 2
Функция, проверяющая, что подстрока <tex>x[p..m - 1]</tex> является префиксом шаблона <tex>x</tex>. Требует <tex>O(m - p)</tex> времени. '''boolean''' isPrefix('''char'''[] x, '''int''' m, '''int'''Примерыp): '''int''' j = 0{| class '''for''' i ="wikitable"p .. m - 1 '''if''' x[i] ! Строка || Значение функции= x[j]|-| abcabcabc || 0, 0, 3, 0, 0, 6, 0, 0, 9 '''return''' false|- ++j| abcabcc || 0, 0, 1, 0, 0, 1, 7|} '''return''' true
Функция для вычисления сдвигов хороших суффиксов. Требует <tex>O(m)</tex> времени, несмотря на вложенный циклциклы в вызываемых функциях, из-за того, что каждый внутренний цикл выполняется только если в худшем случае будет выполняться на каждой позиции <tex>i</tex> заканчивается подстрока равная суффиксу и при этом колне больше, чем <tex>i</tex> раз. Получается арифметическая прогрессия, сумма которой <tex>O(k \cdot m)</tex>, где <tex>k</tex> {{---во итераций равно длине этого суффикса}} константа. Следовательно, получается оценка по времени <tex>O(m)</tex>. '''voidint''' [] preBmGs(string '''char'''[] x, int m) '''int''' i, j, suff[XSIZE]m): '''int''' bmGstable[m] suff = suffixes(x, m) '''forint''' i = 0 .. m - 1 bmGs[i] lastPrefixPosition = m j = 0
'''for''' i = m - 1 .. 0
'''if''' suffisPrefix(x, m, i + 1) lastPrefixPosition = i + 1 table[m - 1 - i] == lastPrefixPosition - i + m - 1 '''whilefor''' j i = 0 .. i < m - 1 - i2 '''ifint''' bmGs[j] =slen = suffixLength(x, m, i) bmGs table[jslen] = m - 1 - i ++jslen '''forreturn''' i = 0 .. m - 2 bmGs[m - 1 - suff[i]] = m - 1 - itable
Основная функция алгоритма Бойера-Мура
'''void''' BM(string x, int m, string '''char'''[] y, '''char'''[] x): '''int ''' n= length(y): '''int''' bmGs[m]= length(x) '''intif''' m == 0 '''return''' bmBc[ASIZE]
<font color=green>//Предварительные вычисления</font>
<font color=green>//Поиск подстроки</font>
'''intfor''' j i = 0 '''while''' j m - 1 .. i <= n - m1 '''int''' i j = m - 1 '''while''' i >= 0 and x[ij] == y[i + ] '''if''' j]== 0 OUTPUT(i) <font color=green>// Найдена подстрока в позиции i</font> '''return'''
--i
==Асимптотики==
