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