code

Karp Rabin

The Karp Rabin algorithm
kr.c
#define REHASH(a, b, h) ((((h) - (a)*d) << 1) + (b))

int search(char *x, int m, char *y, int n) {
   int d, hx, hy, i, j, count;

   count = 0;
   /* Preprocessing */
   for (d = i = 1; i < m; ++i)
      d = (d<<1);

   for (hy = hx = i = 0; i < m; ++i) {
      hx = ((hx<<1) + x[i]);
      hy = ((hy<<1) + y[i]);
   }

   /* Searching */
   j = 0;
   while (j <= n-m) {
      if (hx == hy && memcmp(x, y + j, m) == 0) OUTPUT(j);
      hy = REHASH(y[j], y[j + m], hy);
      ++j;
   }
   return count;
}