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 $P$’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 $R=10$): $h(x_{0}...x_{4})=(x_{0}x_{1}x_{2}x_{3}x_{4})_{10}mod97$

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