code

Wu Manber for Single Pattern Matching

The Wu Manber for Single Pattern Matching algorithm
hash3.c
#define RANK3 3

int search(unsigned char *x, int m, unsigned char *y, int n) {
   int count, j, i, sh, sh1, mMinus1, mMinus2, shift[WSIZE];
   unsigned char h;
   if (m<3) return -1;
   count = 0;
   mMinus1 = m-1;
   mMinus2 = m-2;

   /* Preprocessing */
   for (i = 0; i < WSIZE; ++i)
      shift[i] = mMinus2;

   h = x[0];
   h = ((h<<1) + x[1]);
   h = ((h<<1) + x[2]);
   shift[h] = m-RANK3;
   for (i=RANK3; i < mMinus1; ++i) {
      h = x[i-2];
      h = ((h<<1) + x[i-1]);
      h = ((h<<1) + x[i]);
      shift[h] = mMinus1-i;
   }
   h = x[i-2];
   h = ((h<<1) + x[i-1]);
   h = ((h<<1) + x[i]);
   sh1 = shift[h];
   shift[h] = 0;
   if (sh1==0) sh1=1;


   /* Searching */
   i = mMinus1;
   memcpy(y+n, x, m);
   while (1) {
      sh = 1;
      while (sh != 0) {
         h = y[i-2];
         h = ((h<<1) + y[i-1]);
         h = ((h<<1) + y[i]);
         sh = shift[h];
         i+=sh;
      }
      if (i < n) {
         j=0;
         while(j<m && x[j]==y[i-mMinus1+j]) j++;
         if (j>=m) {
            OUTPUT(i-mMinus1);
         }
         i+=sh1;
      }
      else return count;
   }
}