418
правок
Изменения
→Псевдо-код
Функция для вычисления таблицы сдвигов плохих символов. Она будет равна длине шаблона для всех символов, которые не встречаются в шаблоне, и порядковому номеру с конца для остальных (кроме последнего, для него тоже берется длина шаблона). Вычисляется прямо по определению за <tex>O(m+\sigma)</tex>
'''int'''[] '''preBmBc'''('''string ''' x, '''int ''' m): '''int ''' bmBc[ASIZE];
<font color=green>// Значение по умолчанию = m</font>
'''for ''' i = 0 .. ASIZE-1 bmBc[i] = m; '''for ''' i = 0 .. m - 2 bmBc[x[i]] = m - i - 1; '''return ''' bmBc;
Функция для вычисления таблицы суффиксов. Она находит для каждой позиции в шаблоне <tex>x</tex> максимальную длину суффикса <tex>x</tex>, который повторяется в строке и заканчивается в данной позиции. Например, для строки "'''abcabcabc'''" таблица будет '''0,0,3,0,0,6,0,0,9''', а для строки "'''abcabcc'''" - '''0,0,1,0,0,1,7'''. Также, очевидно, что значение функции для последнего элемента будет равно длине всей строки.
'''int'''[] '''suffixes'''(string x, int m): '''int ''' f= 0 '''int ''' suff[m]
suff[m - 1] = m
'''int ''' g = m - 1
'''for''' i = m - 2 .. 0
'''if''' i > g and suff[i + m - 1 - f] < i - g
suff[i] = suff[i + m - 1 - f]
'''else'''
'''if''' (i < g)
g = i
f = i
--g
suff[i] = f - g
'''return ''' suff
Функция для вычисления сдвигов хороших суффиксов
'''void ''' '''preBmGs'''(string x, int m): '''int ''' i, j, suff[XSIZE]; '''int ''' bmGs[] suff = suffixes(x, m); '''for (''' i = 0; i < .. m; ++i)- 1 bmGs[i] = m; j = 0; '''for ''' i = m - 1 .. 0 '''if (''' suff[i] == i + 1) '''while (''' j < m - 1 - i) '''if (''' bmGs[j] == m) bmGs[j] = m - 1 - i;
++j
'''for ''' i = 0 .. m - 2 bmGs[m - 1 - suff[i]] = m - 1 - i;
Основная функция алгоритма Бойера-Мура
'''void ''' '''BM'''(string x, int m, string y, int n): '''int ''' bmGs[m]; '''int ''' bmBc[ASIZE];
<font color=green>//Предварительные вычисления</font>
bmGs = preBmGs(x, m); bmBc = preBmBc(x, m);
<font color=green>//Поиск подстроки</font>
'''int ''' j = 0; '''while (''' j <= n - m) '''int ''' i = m - 1; '''while (''' i >= 0 and x[i] == y[i + j])
--i
'''if (''' i < 0) OUTPUT(j); <font color=green>// Найдена подстрока в позиции j</font> j += bmGs[0]; <font color=green>//Очевидно, что можем сделать сдвиг на период, т.к. там явно не будет совпадений.</font> '''else''' j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
==Асимптотики==
