code

KMP Skip Search

The KMP Skip Search algorithm
kmpskip.c

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

void preMp(char *x, int m, int mpNext[]) {
   int i, j;

   i = 0;
   j = mpNext[0] = -1;
   while (i < m) {
      while (j > -1 && x[i] != x[j])
         j = mpNext[j];
      mpNext[++i] = ++j;
   }
}

int attempt(char *y, char *x, int m, int start, int wall) {
   int k;
   k = wall - start;
   while (k < m && x[k] == y[k + start])
      ++k;
   return(k);
}

int search(unsigned char *x, int m, unsigned char *y, int n) {
   int i, j, k, kmpStart, per, start, wall, count;
   int kmpNext[XSIZE], list[XSIZE], mpNext[XSIZE], z[SIGMA];

   /* Preprocessing */
   preMp(x, m, mpNext);
   preKmp(x, m, kmpNext);
   memset(z, -1, SIGMA*sizeof(int));
   memset(list, -1, m*sizeof(int));
   z[x[0]] = 0;
   for (i = 1; i < m; ++i) {
      list[i] = z[x[i]];
      z[x[i]] = i;
   }

   /* Searching */
   count = 0;
   wall = 0;
   per = m - kmpNext[m];
   i = j = -1;
   do {
      j += m;
   } while (j < n && z[y[j]] < 0);
   if (j >= n)
     return count;
   i = z[y[j]];
   start = j - i;
   while (start <= n - m) {
      if (start > wall)
         wall = start;
      k = attempt(y, x, m, start, wall);
      wall = start + k;
      if (k == m) {
         OUTPUT(start);
         i -= per;
      }
      else
         i = list[i];
      if (i < 0) {
         do {
            j += m;
         } while (j < n && z[y[j]] < 0);
         if (j >= n)
            return count;
         i = z[y[j]];
      }
      kmpStart = start + k - kmpNext[k];
      k = kmpNext[k];
      start = j - i;
      while (start < kmpStart ||
             (kmpStart < start && start < wall)) {
         if (start < kmpStart) {
            i = list[i];
            if (i < 0) {
               do {
                  j += m;
               } while (j < n && z[y[j]] < 0);
               if (j >= n)
                  return count;
               i = z[y[j]];
            }
            start = j - i;
         }
         else {
            kmpStart += (k - mpNext[k]);
            k = mpNext[k];
         }
      }
   }
   return count;
}