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.