code

Smith

The Smith algorithm
smith.c

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

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

int search(unsigned char *x, int m, unsigned char *y, int n) {
   int j, bmBc[SIGMA], qsBc[SIGMA], count;

   /* Preprocessing */
   preBmBc(x, m, bmBc);
   preQsBc(x, m, qsBc);

   count = 0;
   /* Searching */
   j = 0;
   while (j<= n - m) {
      if (memcmp(x, y + j, m) == 0)
         OUTPUT(j);
      j += MAX(bmBc[y[j + m - 1]], qsBc[y[j + m]]);
   }
   return count;
}