code

Franek Jennings Smyth

The Franek Jennings Smyth algorithm
fjs.c

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

void preKmp(unsigned char *x, int m, int kmpNexy[]) {
   int i, j;
   i = 0;
   j = kmpNexy[0] = -1;
   while (i < m) {
      while (j > -1 && x[i] != x[j])
         j = kmpNexy[j];
      i++;
      j++;
      if (i<m && x[i] == x[j])
         kmpNexy[i] = kmpNexy[j];
      else
         kmpNexy[i] = j;
   }
}

int search( unsigned char *x, int m, unsigned char *y, int n ) {
   int i, s, count, qsbc[SIGMA], kmp[XSIZE];

   /* Preprocessing */
   preQsBc(x,m,qsbc);
   preKmp(x,m,kmp);

   /* Searching */
   s = 0;
   count = 0;
   while(s<=n-m) {
      while(s<=n-m && x[m-1]!=y[s+m-1]) s+=qsbc[y[s+m]];
      if (s>n-m) return count;
      i=0; 
      while(i<m && x[i]==y[s+i]) i++;
      if (i>=m) count++;
      s+=(i-kmp[i]);
   }
   return count;
}