Skip to content

Instantly share code, notes, and snippets.

@jcppkkk jcppkkk/gist:4149704
Created Nov 26, 2012

Embed
What would you like to do?
Boyer-Moore algorithm
#define MAX(a,b) \
({ __typeof__ (a) _a = (a); \
__typeof__ (b) _b = (b); \
_a > _b ? _a : _b; })
#include <stdio.h>
#include <string.h>
#define XSIZE 20
#define ASIZE 256
void preBmBc(char *x, int m, int bmBc[]) {
int i;
for (i = 0; i < ASIZE; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1 ; ++i)
bmBc[x[i]] = m - i - 1;
}
void suffixes(char *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 && 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 && x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
}
}
}
void preBmGs(char *x, int m, int bmGs[]) {
int i, j, suff[XSIZE];
suffixes(x, m, suff);
for (i = 0; i < m; ++i)
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= 0; --i)
if (suff[i] == i + 1)
for (; j < m - 1 - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
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);
puts("bmBc:");
for (i = 0; i < 256 ; ++i)
if(bmBc[i]!=m)
printf("%c ", i);
puts("");
for (i = 0; i < 256 ; ++i)
if(bmBc[i]!=m)
printf("%d ", bmBc[i]);
puts("");
puts("BmGs:");
for (i = 0; i < m ; ++i)
printf("%d ", i);
puts("");
for (i = 0; i < m ; ++i)
printf("%d ", bmGs[i]);
puts("");
puts("matched index:");
/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
if (i < 0) {
printf("%d\n", j);
j += bmGs[0];
}
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
}
int main (){
char x[] = "gcagagag";
char y[] = "gcatcgcagagagtatacagtacg";
BM(x, strlen(x), y, strlen(y) );
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.