code

Fast Search

The Fast Search algorithm
fs-w2.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 *P, int m, unsigned char *T, int n)
{
   int i,j,s1,s2,k,h,count,hbcr[SIGMA],hbcl[SIGMA],gsR[XSIZE],gsL[XSIZE];
   unsigned char c,Pr[XSIZE],P2[XSIZE];

   /* prprocessing */
   for (i=0;i<SIGMA;i++) hbcr[i]=m;
   for (i=0;i<m;i++) hbcr[P[i]] = (m-i-1);

   for (i=0;i<SIGMA;i++) hbcl[i]=m;
   for (i=0;i<m;i++) hbcl[P[m-1-i]] = (m-i-1);

   for (i=0; i<m; i++) Pr[i]=P[m-1-i]; Pr[m]='\0';
Pre_GS(P,  m, gsR);
Pre_GS(Pr, m, gsL);
   
   unsigned char lastch = P[m-1], firstch=P[0];
   int mm1 = m-1;

   /* searching */
   int q = n/2;
s1 = mm1; s2 = n-m;
count = 0;
   k=hbcr[T[s1]];
   h=hbcl[T[s2]];
   while(s1 <= s2+mm1) {
      if (!k) { 
         j = mm1; k=s1-mm1;
         while(j>=0 && P[j]==T[k+j]) j--;
         if (j<0) count++;
         s1+=gsR[j+1];
      }
      if (!h) { 
         i = 0; 
         while(i<m && P[i]==T[s2+i]) i++;
         if (i==m) count++;
         s2-=gsL[m-i];
      }
      while( (k=hbcr[T[s1]]) && (h=hbcl[T[s2]]) ) {
         s1+=k; 
         s2-=h; 
      }
   }
   return count;
}