code

Zhu Takaoka

The Zhu Takaoka algorithm
zt.c

void suffixes(unsigned char *x, int m, int *suff) {
   int f, g, i;
 
   suff[m - 1] = m;
   g = m - 1;
   for (i = m - 2; i >= 0; --i) {
      if (i > g && suff[i + m - 1 - f] < i - g)
         suff[i] = suff[i + m - 1 - f];
      else {
         if (i < g)
            g = i;
         f = i;
         while (g >= 0 && x[g] == x[g + m - 1 - f])
            --g;
         suff[i] = f - g;
      }
   }
}
 
void preBmGs(unsigned char *x, int m, int bmGs[]) {
   int i, j, suff[XSIZE];
 
   suffixes(x, m, suff);
 
   for (i = 0; i < m; ++i)
      bmGs[i] = m;
   j = 0;
   for (i = m - 1; i >= 0; --i)
      if (suff[i] == i + 1)
         for (; j < m - 1 - i; ++j)
            if (bmGs[j] == m)
               bmGs[j] = m - 1 - i;
   for (i = 0; i <= m - 2; ++i)
      bmGs[m - 1 - suff[i]] = m - 1 - i;
}

 void preZtBc(unsigned char *x, int m, int ztBc[SIGMA][SIGMA]) {
   int i, j;

   for (i = 0; i < SIGMA; ++i)
      for (j = 0; j < SIGMA; ++j)
         ztBc[i][j] = m;
   for (i = 0; i < SIGMA; ++i)
      ztBc[i][x[0]] = m - 1;
   for (i = 1; i < m - 1; ++i)
      ztBc[x[i - 1]][x[i]] = m - 1 - i;
}

int search(unsigned char *x, int m, unsigned char *y, int n) {
   int i, j, ztBc[SIGMA][SIGMA], bmGs[XSIZE], count;

   /* Preprocessing */
   preZtBc(x, m, ztBc);
   preBmGs(x, m, bmGs);
   for (i=0; i<m; i++) y[n+i]=y[n+m+i]=x[i];

   /* Searching */
   count = 0;
   j = 0;
   while (j <= n - m) {
      i = m - 1;
      while (i >=0 && x[i] == y[i + j])
         --i;
      if (i < 0) {
         OUTPUT(j);
         j += bmGs[0];
      }
      else
         j += MAX(bmGs[i],ztBc[y[j + m - 2]][y[j + m - 1]]);
   }
   return count;
}