418
правок
Изменения
Нет описания правки
[[Файл:boyer-moore-algorithm-4.gif|450px|thumb|center|'''Сдвиг плохого символа''', символ <tex>b</tex> не входит в <tex>x</tex>.]]
Обратите внимание, что сдвиг плохого символ символа может быть отрицательным, таким образом для сдвига окна сравнения алгоритм Бойера-Мура использует значение, равное максимуму между сдвигом хорошего суффикса и сдвига плохого символа. Более формально две функции сдвигов определяются следующим образом:
Пусть значения функции сдвига хорошего суффикса хранятся в таблице массиве <tex>bmGs</tex> размером <tex>m+1</tex>.
Определим два условия:
Тогда для всех <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>suff</tex>, определенную определенный так:
для всех <tex>i</tex> таких, что <tex>1 \leqslant i < m</tex> выполняется <tex>suff[i]=\max\{k : x[i-k+1 .. i]=x[m-k .. m-1]\}</tex>
int[] '''preBmBc'''(string x, int m):
int bmBc[ASIZE];
<font color=green>// Значение по умолчанию = m</font>
for i = 0 .. ASIZE-1
bmBc[i] = 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)
--i
if (i < 0)
OUTPUT(j); <font color=green>// Найдена подстрока в позиции <tex>j</texfont> j += bmGs[0]; <font color=green>//Очевидно, что можем сделать сдвиг на период, т.к. там явно не будет совпадений.</font>
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
* [http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm Wikipedia:Boyer–Moore string search algorithm]
* [http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140 Boyer-Moore algorithm]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Поиск подстроки в строке]]
