code

Factorized Shift And

The Factorized Shift And algorithm
ksa.c
#define CHAR_BIT 8
#define WORD_TYPE unsigned int
#define WORD_BITS (sizeof(WORD_TYPE)*CHAR_BIT)

int search(const unsigned char *x, int m, const unsigned char *y, int n)
{
   int i, j, k, m1;
   int beg, end;
   WORD_TYPE D, D_, M;
   WORD_TYPE B[SIGMA][SIGMA] = {{0}};
   WORD_TYPE L[SIGMA] = {0};
   unsigned count = 0;
   unsigned char c;

   /* Preprocessing */
   end = 1;
   for (k = 1; k < WORD_BITS-1; k++) {
      char occ[SIGMA] = {0};
      while (end < m && occ[x[end]] == 0) {
         occ[x[end]] = 1;
         end++;
      }
   }
   m1 = end;
   k = 1;
   beg = 1;
   end = 1;
   B[x[0]][x[1]] = 1;
   L[x[0]] = 1;
   for (;;) {
      char occ[SIGMA] = {0};
      while (end < m1 && occ[x[end]] == 0) {
         occ[x[end]] = 1;
         end++;
      }
      for (i = beg+1; i < end; i++)
         B[x[i-1]][x[i]] |= 1 << k;
      if (end < m1) {
         B[x[end-1]][x[end]] |= 1 << k;
         L[x[end-1]] |= 1 << k;
      } else {
         M = 1 << k;
         if (end > beg+1) {
            L[x[end-2]] |= 1L << k;
            M <<= 1;
         }
         break;
      }
      beg = end;
      k++;
   }

   /* Searching */
   D = 0;
   c = y[0];
   for (j = 1; j < n; j++) {
      D = (D|1) & B[c][y[j]];
      D_ = D & L[c];
      D += D_;
      c = y[j];
      if (D & M) {
         if (!strncmp(x+m1, y+j+1, m-m1)) {
            count++;
         }
      }
   }
   return count;
}