code

Backward Fast Search, Fast Boyer Moore

The Backward Fast Search, Fast Boyer Moore algorithm
bfs.c

void PreBFS(unsigned char *x, int m, int bm_gs[XSIZE][SIGMA]) {
   int i, j, p, c, h, last, suffix_len, temp[XSIZE];
   suffix_len = 1;
   last = m-1;
   for (i=0;i<=m;i++) for (j=0; j<SIGMA;j++) bm_gs[i][j] = m;
   for (i=0; i<=m; i++) temp[i]=-1;
   for (i=m-2; i>=0; i--)
   if (x[i]==x[last]) {
      temp[last]=i;
      last = i;
   }
   suffix_len++;
   while(suffix_len<=m) {
      last = m-1;
      i = temp[last];
      while(i>=0) {
         if (i-suffix_len+1>=0) {
            if (x[i-suffix_len+1]==x[last-suffix_len+1]) {
               temp[last]=i;
               last=i;
            }
            if (bm_gs[m-suffix_len+1][x[i-suffix_len+1]]>m-1-i) bm_gs[m-suffix_len+1][x[i-suffix_len+1]]=m-1-i;
         }
         else {
            temp[last]=i;
            last = i;
            for (c=0; c<SIGMA; c++)
            if (bm_gs[m-suffix_len+1][c]>m-1-i) bm_gs[m-suffix_len+1][c]=m-1-i;
         }
         i = temp[i];
      }
      temp[last]=-1;
      suffix_len++;
   }
}

int search(unsigned char *x, int m, unsigned char *y, int n)
{
   int i, j, k, s, count, gs[XSIZE][SIGMA], bc[SIGMA];
   int *last, first;
   char ch = x[m-1];

   /* Preprocessing */    
   for (i=0;i<SIGMA;i++) bc[i]=m;
   for (i=0;i<m;i++) bc[x[i]]=m-i-1;
   for (i=0;i<m;i++) y[n+i]=x[i];
   PreBFS(x, m, gs);

   /* Searching */   
   count = 0;
   s=m-1;
   last = gs[m];
   first = gs[1][x[0]];
   while(s<n) {
      while((k=bc[y[s]])!=0)   s = s + k;
      for (j=s-1, k=m-1; k>0 && x[k-1]==y[j]; k--, j--);
      if ( k==0 ) {
         if (s<n) count++;
         s += first;
      }
      else s += gs[k][y[j]];
   }
   return count;
}