Boyer-Moore algorithm

gistfile1.c

#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;
}