code

Horspool

The Horspool algorithm
hor.c

void Pre_Horspool(unsigned char *P, int m, int hbc[]) {
   int i;
   for (i=0;i<SIGMA;i++)   hbc[i]=m;
   for (i=0;i<m-1;i++) hbc[P[i]]=m-i-1;
}


int search(unsigned char *P, int m, unsigned char *T, int n) {
   int i, s, count, hbc[SIGMA];
   Pre_Horspool(P, m, hbc);

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