code

Quick Search

The Quick Search algorithm
qs.c

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

int search(unsigned char *P, int m, unsigned char *T, int n) {
   int i, s, count, qsbc[SIGMA];
   
   /* Preoprocessing */
   preQsBc(P, m, qsbc);

   /* 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+=qsbc[T[s+m]];
   }
   return count;
}