code

Fast Search

The Fast Search algorithm
fs-w4.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,s3,s4,k1,k2,k3,k4,i1,i2,i3;
int h, count, hbcr[SIGMA], hbcl[SIGMA], gsR[XSIZE], gsL[XSIZE];
   unsigned char c, Pr[XSIZE];

/* proprocessing */
   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);

   for (i=0; i<m; i++) T[n+i]=P[i];
   int mm1 = m-1;

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