418
правок
Изменения
м
→Псевдо-код
==Псевдо-код==
Константой <tex>ASIZE</tex> обозначим размер нашего алфавита. Функция для вычисления таблицы сдвигов плохих символов. Вычисляется прямо по определению за <tex>O(m+\sigma)</tex>
int[] '''preBmBc'''(string x, int m):
int bmBc[ASIZE];
Основная функция алгоритма Бойера-Мура
void '''BM'''(char *x, int m, char *y, int n):
int i, j, bmGs[XSIZEm], ; int bmBc[ASIZE];
//Предварительные вычисления
//Поиск подстроки
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);// Найдена подстрока в позиции <tex>j</tex> j += bmGs[0];//Очевидно, что можем сделать сдвиг на период, т.к. там явно не будет совпадений.
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
