String Hashing and Rabin-Karp: Pattern Matching for Interviews

When a coding interview asks you to find a pattern inside a text string, writing a nested loop with O(n * m) time complexity will fail on hidden test cases with lengths up to 10^5. You should use polynomial string hashing and the Rabin-Karp algorithm to reduce the search down to average O(n + m) time.

Why Polynomial Hashing Beats Naive Search

Checking every possible starting index of a pattern in a text wastes processor cycles. Instead of comparing characters one by one at index i, you convert each substring into a single integer using a polynomial function.

Take the string abc with lowercase English letters. Assign a = 1, b = 2, c = 3. The hash value is 1 * 31^2 + 2 * 31^1 + 3 * 31^0. Calculate that out: 31^2 is 961, multiplied by 1 is 961. Add 2 * 31, which is 62. Add 3, which gives a total hash of 1026.

If you shift your window by one character to check the next substring, recalculating that sum from scratch takes O(m) time. That brings your total time back up to O(n * m).

The Rolling Hash Mechanism

Rabin-Karp avoids recalculating the whole sum by using a rolling hash. Subtract the contribution of the old leading character, multiply the remainder by your base prime, and add the new trailing character.

For example, if your base is 31 and modulus is 1e9 + 7, sliding the window of length 3 from abc to bcd removes the term for a multiplied by 31^2, shifts the remaining powers down by one position, and adds the numeric value of d. This update step runs in O(1) time.

You compute the hash of the pattern once. Then you slide through the text hash array in linear time.

Managing Hash Collisions

Two different strings can produce the exact same hash value because the number of possible strings is larger than your modulus. When your integer hashes match during an interview problem like searching for foo in foobar, you must write a direct character check for that specific index window before recording a successful match.

To keep collision rates near zero, pick a large prime modulus like 1000000007 and a base larger than your alphabet size, such as 31 for lowercase letters or 53 for mixed case. Avoid using a single small multiplier or a power of two modulus, because repetitive patterns will generate predictable collisions.

Rabin-Karp Versus KMP

The Knuth-Morris-Pratt algorithm builds a longest prefix suffix array to avoid unnecessary backups, guaranteeing O(n + m) worst-case time without any hash collisions. Rabin-Karp achieves average O(n + m) time, but its worst-case degrades to O(n * m) if malicious test cases trigger constant hash collisions.

Choose Rabin-Karp when you need to find multiple patterns at once using a hash set, or when solving problems involving repeated substrings of a fixed length like finding the longest duplicate substring with binary search. KMP is strictly better for a single pattern search where worst-case guarantees matter more than implementation speed.

Practice rolling hash mechanics on medium string problems using DSA Tracker to test your modulo arithmetic edge cases before your next online assessment.

Keep going with the step-by-step visualizer and practice problems.

Further reading: Binary search on Wikipedia.