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 $\to$ 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}\mathrm{mod}97$

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

Related

• Boyer-Moore Algorithm