Karp-Rabin algorithm

Hashing provides a simple method to avoid a quadratic number of character comparisons in most practical situations. Instead of checking at each position of the text if the pattern occurs, it seems to be more efficient to check only if the contents of the window “looks like” the pattern. In order to check the resemblance between these two words an hashing function is used.

To be helpful for the string matching problem an hashing function hash should have the following properties:

efficiently computable;

highly discriminating for strings;

hash(y[j+1 .. j+m]) must be easily computable from hash(y[j .. j+m-1]) and y[j+m]:   hash(y[j+1 .. j+m])= rehash(y[j], y[j+m], hash(y[j .. j+m-1]).

For a word w of length m let hash(w) be defined as follows:
hash(w[0 .. m-1])=(w[0]*2^m-1+ w[1]*2^m-2+···+ w[m-1]*2⁰) mod q
where q is a large number.

Then, rehash(a,b,h)= ((h-a*2^m-1)*2+b) mod q

The preprocessing phase of the Karp-Rabin algorithm consists in computing hash(x). It can be done in constant space and O(m) time.

During searching phase, it is enough to compare hash(x) with hash(y[j .. j+m-1]) for 0  j < n-m. If an equality is found, it is still necessary to check the equality x=y[j .. j+m-1] character by character.

The time complexity of the searching phase of the Karp-Rabin algorithm is O(mn) (when searching for a^m in aⁿ for instance). Its expected number of text character comparisons is O(n+m).

#define REHASH(a, b, h) ((((h) - (a)*d) << 1) + (b))

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

   /* Preprocessing */
   /* computes d = 2^(m-1) with
      the left-shift operator */
   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;
   }

}