code

Reverse Colussi

The Reverse Colussi algorithm
rcol.c

void preRc(unsigned char *x, int m, int h[], int rcBc[SIGMA][XSIZE], int rcGs[]) {
   int a, i, j, k, q, r, s,
   hmin[XSIZE], kmin[XSIZE], link[XSIZE],
   locc[SIGMA], rmin[XSIZE];
 
   for (a = 0; a < SIGMA; ++a)
      locc[a] = -1;
   link[0] = -1;
   for (i = 0; i < m - 1; ++i) {
      link[i + 1] = locc[x[i]];
      locc[x[i]] = i;
   }

   for (a = 0; a < SIGMA; ++a)
      for (s = 1; s <= m; ++s) {
         i = locc[a];
         j = link[m - s];
         while (i - j != s && j >= 0)
            if (i - j > s)
               i = link[i + 1];
            else
               j = link[j + 1];
         while (i - j > s)
            i = link[i + 1];
         rcBc[a][s] = m - i - 1;
      }
 
   k = 1;
   i = m - 1;
   while (k <= m) {
      while (i - k >= 0 && x[i - k] == x[i])
         --i;
      hmin[k] = i;
      q = k + 1;
      while (hmin[q - k] - (q - k) > i) {
         hmin[q] = hmin[q - k];
         ++q;
      }
      i += (q - k);
      k = q;
      if (i == m)
         i = m - 1;
   }
 
   memset(kmin, 0, m * sizeof(int));
   for (k = m; k > 0; --k)
      kmin[hmin[k]] = k;
 
   for (i = m - 1; i >= 0; --i) {
      if (hmin[i + 1] == i)
         r = i + 1;
      rmin[i] = r;
   }
 
   i = 1;
   for (k = 1; k <= m; ++k)
      if (hmin[k] != m - 1 && kmin[hmin[k]] == k) {
         h[i] = hmin[k];
         rcGs[i++] = k;
      }
   i = m-1;
   for (j = m - 2; j >= 0; --j)
      if (kmin[j] == 0) {
         h[i] = j;
         rcGs[i--] = rmin[j];
      }
   rcGs[m] = rmin[0];
}
 
 
int search(unsigned char *x, int m, unsigned char *y, int n) {
   int i, j, s, rcBc[SIGMA][XSIZE], rcGs[XSIZE], h[XSIZE], count;
 
   /* Preprocessing */
   preRc(x, m, h, rcBc, rcGs);
 
   /* Searching */
   count = 0;
   j = 0;
   s = m;
   while (j <= n - m) {
      while (j <= n - m && x[m - 1] != y[j + m - 1]) {
         s = rcBc[y[j + m - 1]][s];
         j += s;
      }
      for (i = 1; i < m && x[h[i]] == y[j + h[i]]; ++i);
      if (i >= m && j<=n-m)
         OUTPUT(j);
      s = rcGs[i];
      j += s;
   }
   return count;
}