418
правок
Изменения
м
}
}
for while (; j < m - 1 - i; ++j)
}
}
→Псевдо-код
==Псевдо-код==
Функция для вычисления таблицы сдвигов плохих символов
void '''preBmBc'''(char *string x, int m, int bmBc[]):
for i = 0 .. ASIZE-1
bmBc[i] = m
Функция для вычисления таблицы суффиксов
void '''suffixes'''(char *string x, int m, int *suff):
int f, g, i;
suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= .. 0; --i) { 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;
while (g >= 0 && and x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
Функция для вычисления сдвигов хороших суффиксов
void '''preBmGs'''(char *string x, int m, int bmGs[]):
int i, j, suff[XSIZE];
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= .. 0; --i)
if (suff[i] == i + 1)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
++j for (i = 0; i <= .. m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
Основная функция алгоритма Бойера-Мура
void '''BM'''(char *x, int m, char *y, int n):
int i, j, bmGs[XSIZE], bmBc[ASIZE];
//Поиск подстроки
j = 0;
while (j <= n - m) { for (i = m - 1; while (i >= 0 && and x[i] == y[i + j]; ) --i); if (i < 0) {
OUTPUT(j);
j += bmGs[0];
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
==Сравнение с другими алгоритмами==
