code

Skip Search

The Skip Search algorithm
skip.c
#include "include/AUTOMATON.h"

int search(unsigned char *x, int m, unsigned char *y, int n) {
   int i, j, count, h, k;
   List ptr, z[SIGMA];

   /* Preprocessing */
   memset(z, 0, SIGMA*sizeof(List));
   for (i = 0; i < m; ++i) {
      ptr = (List)malloc(sizeof(struct _cell));
      if (ptr == NULL)
         error("SKIP");
      ptr->element = i;
      ptr->next = z[x[i]];
      z[x[i]] = ptr;
   }
  
   count = 0;
   /* Searching */
   for (j = m - 1; j < n; j += m)
      for (ptr = z[y[j]]; ptr != NULL; ptr = ptr->next) 
if ((j-ptr->element) <= n-m) {
k = 0;
h = j-ptr->element;
while(k<m && x[k]==y[h+k]) k++;
if (k>=m) count++;
          //if (memcmp(x, y + j - ptr->element, m) == 0) {
         //   if (j - ptr->element <= n - m)
         //      OUTPUT(j - ptr->element);
          }
         //else
         //   break;
   //}
   return count;
}