code

Forward Fast Search

The Forward Fast Search algorithm
ffs.c

void Forward_Suffix_Function(unsigned char *x, int m, int bm_gs[XSIZE][SIGMA], int alpha) {
   int init;
   int i, j, last, suffix_len, temx[XSIZE];
   init = 0;
   for (i=0;i<m;i++) for (j=init; j<init+alpha;j++) bm_gs[i][j] = m+1;
   for (i=0; i<m; i++) temx[i]=i-1;
   for (suffix_len=0; suffix_len<=m; suffix_len++) {
      last = m-1;
      i = temx[last];
      while(i>=0) {
         if ( bm_gs[m-suffix_len][x[i+1]]>m-1-i )
            if (i-suffix_len<0 || (i-suffix_len>=0 && x[i-suffix_len]!=x[m-1-suffix_len]))
               bm_gs[m-suffix_len][x[i+1]]=m-1-i;
         if ((i-suffix_len >= 0 && x[i-suffix_len]==x[last-suffix_len]) || (i-suffix_len <  0)) {
            temx[last]=i;
            last=i;
         }
         i = temx[i];
      }
      if (bm_gs[m-suffix_len][x[0]] > m) bm_gs[m-suffix_len][x[0]] = m;
      temx[last]=-1;
   }
}

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

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

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