code

Boyer Moore Horspoolusing Probabilities

The Boyer Moore Horspoolusing Probabilities algorithm
pbmh.c

int search(unsigned char *x, int m, unsigned char *y, int n, int *FREQ)
{
   int i, j, s, tmp, count, hbc[SIGMA], v[XSIZE];

   /* Preprocessing */
   for (i=0; i<m; i++) v[i]=i;
   for (i=m-1; i>0; i--)
      for (j=0; j<i; j++)
         if (FREQ[x[v[j]]]>FREQ[x[v[j+1]]]) {   
            tmp = v[j+1];
            v[j+1] = v[j];
            v[j] = tmp;
         }
   for (i=0;i<SIGMA;i++)   hbc[i]=m;
   for (i=0;i<m-1;i++) hbc[x[i]]=m-i-1;

   /* Searching */
   s = 0;
   count = 0;
   while(s<=n-m) {
      i=0;
      while(i<m && x[v[i]]==y[s+v[i]]) i++;
      if (i==m) count++;
      s+=hbc[y[s+m-1]];
   }
   return count;
}