code

Fast Search

The Fast Search algorithm
fs.c

void Pre_GS(unsigned char *x, int m, int bm_gs[]) {
   int i, j, p, f[XSIZE];
   for (i=0;i<XSIZE;i++) bm_gs[i]=0;
   f[m]=j=m+1;
   for (i=m; i > 0; i--) {
      while (j <= m && x[i-1] != x[j-1]) {
         if (bm_gs[j] == 0) bm_gs[j]=j-i;
         j=f[j];
      }
      f[i-1]=--j;
   }
   p=f[0];
   for (j=0; j <= m; ++j) {
      if (bm_gs[j] == 0) bm_gs[j]=p;
      if (j == p) p=f[p];
   }
}

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

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

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