Back to Study Material Data Structures and Algorithms

Rabin Karp Algorithm

The Rabin-Karp algorithm uses hashing to perform pattern matching with an expected O(n plus m) running time. Developed by Richard Karp and Michael Rabin in...

Rabin Karp Algorithm

Rolling Hash Pattern Matching and Multiple Pattern Search

The Rabin-Karp algorithm uses hashing to perform pattern matching with an expected O(n plus m) running time. Developed by Richard Karp and Michael Rabin in 1987, it is particularly well-suited to the multiple pattern search problem, where you need to find any of k patterns simultaneously in a text.

The algorithm computes a hash of the pattern P and compares it to the hash of every sliding window of length m in the text T. If the hashes match, a character-by-character verification confirms a true match, ruling out hash collisions. If the hashes do not match, no verification is needed and the window slides forward.

The efficiency depends on computing the window hash incrementally. For a polynomial hash where the hash of a string S is (S[0] times b^(m-1) plus S[1] times b^(m-2) plus ... plus S[m-1]) modulo q for some base b and large prime q, moving the window from position i to i plus one can be done in O(1): subtract the contribution of S[i] (the character leaving the window), multiply the running total by b, and add S[i plus m] (the character entering). This rolling hash makes each window transition O(1).

Hash collisions occur when two different strings have the same hash. Each collision requires an O(m) verification step. By choosing q large and b random, the probability of a collision on any specific comparison is 1 divided by q, which is negligible. In practice, the expected total number of spurious hits is O(n divided by q), which is O(1) for large q. The expected total time is therefore O(n plus m).

For searching k patterns simultaneously, compute all k pattern hashes and store them in a hash set. Each window hash is checked against the set in O(1) average time. A match triggers O(m) verification. The total expected time is O(n plus m times k) for preprocessing and O(n) for the search phase, compared to O(n times m times k) for naive multi-pattern matching.

Worst-case time for Rabin-Karp is O(n times m) when every window hash matches the pattern hash due to collisions, but this is astronomically unlikely with a good hash function and large modulus.

Worked example: text "ABRACADABRA", pattern "ABRA". With hash values computed mod 101 using base 26, the rolling hash quickly identifies candidate positions 0 and 7 for verification, confirming both matches in minimal total comparisons.

Interview tip: Rabin-Karp is the go-to algorithm for plagiarism detection (detecting copied k-word phrases) and DNA sequence matching over multiple query sequences. Mention this application when discussing the algorithm to show breadth of knowledge.