Pattern Matching (String Algorithms)

Karp-Rabin Algorithm

The idea of the Karp-Rabin Fingerprint Algorithm is to use Hashing to eliminate guesses.

We compute fingerprint (hash function) for each guess, and if different from ’s fingerprint, then the guess cannot be an occurrence no need to do a string-compare.

We use a standard hash-function: flattening + modular (radix ):

The crucial insight is that we can update the fingerprints in constant time.