Rabin-Karp Algorithm — Rolling Hash

We've seen how the naive algorithm compares patterns character by character, and how the KMP algorithm cleverly uses prefix information to avoid redundant comparisons. But what if we could take an entirely different approach—one that doesn't compare characters at all?

The radical insight: Instead of asking "do these two strings have the same characters?", what if we asked "do these two strings have the same fingerprint?"

This is the foundational idea behind the Rabin-Karp algorithm, developed by Michael O. Rabin and Richard M. Karp in 1987. Rather than comparing strings directly, we compute a hash value (a numerical fingerprint) for both the pattern and each candidate substring in the text. If the hash values match, we have a potential match; if they differ, we can instantly rule out that position.

Before introducing the hashing approach, let's crystallize exactly what makes string comparison expensive and why a different paradigm might help.

The fundamental challenge:

When we compare a pattern P of length m against a substring of text T, the naive approach examines characters one by one:

Pattern:    A B C D E
Substring:  A B C D X
            ✓ ✓ ✓ ✓ ✗

Each comparison costs O(1), but we might need up to m comparisons before discovering a mismatch—and that mismatch might occur at the very last character. For n-m+1 possible starting positions, this yields O(nm) total work in the worst case.

Why this matters:

The core inefficiency isn't just the character comparisons—it's that we learn nothing global from local comparisons. When we compare ABCDE against ABCDX and find they differ at position 5, we've gained no information about how ABCDE compares to any other substring. We start from scratch at the next position.

The key observation:

What if, instead of character-by-character comparison, we could reduce each m-character string to a single number? Then string comparison becomes integer comparison—a single O(1) operation, regardless of string length.

This is precisely what hash functions enable.

A hash function is a mathematical function that maps data of arbitrary size to fixed-size values. For string matching, we need a hash function h that takes a string and produces an integer:

h("HELLO") → 7429831
h("WORLD") → 2198457
h("HELLO") → 7429831  (same input always gives same output)

Essential properties for string matching:

The hash-based comparison paradigm:

With a good hash function, our pattern matching strategy becomes:

1. Compute hash(pattern) — the fingerprint we're looking for
2. For each position i in text:
   • Compute hash(text[i:i+m]) — fingerprint of current substring
   • If hashes differ → definitely not a match, move on
   • If hashes match → possibly a match, verify with character comparison

Step 3 is crucial: matching hashes don't guarantee matching strings (due to collisions), but differing hashes do guarantee non-matching strings. We use hash comparison as a fast filter.

To understand the power of hashing, we need to analyze what happens in the best case versus the worst case for pattern matching.

Naive approach analysis:

• At each position, we compare up to m characters
• n-m+1 positions to check
• Worst case: O(nm) total comparisons
• Most comparisons are wasted on non-matching substrings

Hash-based approach analysis:

• Compute pattern hash once: O(m)
• At each position, compare two integers: O(1)
• n-m+1 positions to check: O(n) hash comparisons
• Only verify (with O(m) character comparison) when hashes match

The key insight: Most positions won't match. If hashes are uniformly distributed and collisions are rare, the hash comparison filters out nearly all non-matching positions in O(1) each.

A concrete example:

Suppose we're searching for a 100-character pattern in a 1,000,000-character text.

Naive approach (worst case):

• ~999,901 positions × 100 comparisons = ~100 million character comparisons

Hash-based approach (expected case):

• 1 pattern hash computation: 100 operations
• ~999,901 hash comparisons: ~1 million integer comparisons
• Assume collision rate of 1/1,000,000: maybe 1-2 false positives to verify
• Total: ~1 million operations

The hash-based approach is approximately 100× faster in expected case, scaling with text length rather than the product of text and pattern lengths.

There's a critical problem with the naive hashing approach we've described so far. Let's think carefully about the cost of computing hash values.

The hidden cost:

If computing hash(text[i:i+m]) requires reading all m characters of the substring, then computing hashes for all n-m+1 positions costs:

(n - m + 1) × m = O(nm)

This is exactly as expensive as the naive algorithm! We've gained nothing.

The critical question:

Can we compute the hash of text[i+1:i+1+m] more efficiently if we already know the hash of text[i:i+m]?

In other words: can we update a hash value incrementally as our window slides, rather than recomputing it from scratch?

The sliding window insight:

Consider two consecutive substrings of text:

Position i:   [a₁ a₂ a₃ ... aₘ]
Position i+1:    [a₂ a₃ ... aₘ aₘ₊₁]

These substrings share m-1 characters. A clever hash function should be able to:

1. "Remove" the contribution of a₁ (the character leaving the window)
2. "Add" the contribution of aₘ₊₁ (the character entering the window)

If both operations take O(1) time, then updating the hash takes O(1) time, and computing all n-m+1 hashes takes only O(n) time total.

This is the essence of the rolling hash technique that we'll explore in detail in the next page.

Before introducing the polynomial rolling hash, let's examine a simpler hash function to build intuition about why hash design matters.

Sum-based hash:

The simplest hash function just sums the character values:

hash("ABC") = ord('A') + ord('B') + ord('C') = 65 + 66 + 67 = 198

Advantages:

• Easy to compute: O(m) for a string of length m
• Easy to update: hash("BCD") = hash("ABC") - ord('A') + ord('D') = O(1)

Fatal flaw:

• Produces the same hash for any permutation of characters
• hash("ABC") = hash("BAC") = hash("CBA") = 198
• Collision rate is catastrophically high

Why position matters:

The sum-based hash fails because it ignores character positions. In pattern matching, "ABC" and "CBA" are completely different strings that should never match. We need a hash function where character positions affect the output.

The solution:

Polynomial hashing treats the string as a number in some base b, where each character's position determines its weight:

hash("ABC") = ord('A')×b² + ord('B')×b¹ + ord('C')×b⁰

Now "ABC" and "CBA" produce different hashes because characters at different positions contribute differently. This is the foundation of the rolling hash we'll explore next.

The solution to our collision problem is the polynomial hash function, which treats strings as numbers in a chosen base. This is the hash function used by Rabin-Karp and many other string algorithms.

Definition:

For a string s = s₀s₁s₂...sₘ₋₁ of length m, the polynomial hash is:

hash(s) = (s₀ × bᵐ⁻¹ + s₁ × bᵐ⁻² + ... + sₘ₋₂ × b¹ + sₘ₋₁ × b⁰) mod q

Where:

• b is the base (typically a prime slightly larger than the alphabet size)
• q is a large prime modulus (to keep hash values bounded)
• sᵢ is the numerical value of character at position i

Why this works:

Consider hashing "ABC" with base b = 31:

hash("ABC") = 65×31² + 66×31¹ + 67×31⁰
            = 65×961 + 66×31 + 67×1
            = 62465 + 2046 + 67
            = 64578

hash("CBA") = 67×31² + 66×31¹ + 65×31⁰
            = 67×961 + 66×31 + 65×1
            = 64387 + 2046 + 65
            = 66498

Different hashes for different strings!

The polynomial hash we've just seen has a crucial property: it can be updated in O(1) time as our window slides. Let's understand why this works mathematically.

The rolling hash update formula:

Suppose we have computed:

H₁ = hash(s[i:i+m]) = s[i]×bᵐ⁻¹ + s[i+1]×bᵐ⁻² + ... + s[i+m-1]×b⁰

We want to compute:

H₂ = hash(s[i+1:i+1+m]) = s[i+1]×bᵐ⁻¹ + s[i+2]×bᵐ⁻² + ... + s[i+m]×b⁰

The relationship between them:

H₂ = (H₁ - s[i]×bᵐ⁻¹) × b + s[i+m]

Breaking this down:

1. Subtract: Remove the leftmost character's contribution: s[i]×bᵐ⁻¹
2. Shift: Multiply by b to shift all remaining terms one position left
3. Add: Add the new rightmost character: s[i+m]×b⁰

All three operations are O(1) (assuming we precompute bᵐ⁻¹).

Visual representation:

Window at position i:     [A][B][C][D][E]
                           ↓  ↓  ↓  ↓  ↓
Hash components:          A×b⁴ + B×b³ + C×b² + D×b¹ + E×b⁰

Slide window right:          [B][C][D][E][F]
                              ↓  ↓  ↓  ↓  ↓
New hash:                    B×b⁴ + C×b³ + D×b² + E×b¹ + F×b⁰

Update formula:
1. Remove A's contribution: (old_hash - A×b⁴)
2. Shift left:              × b
3. Add F at rightmost:      + F×b⁰

This transformation takes constant time regardless of window size. A 10-character window updates as quickly as a 10,000-character window.

Now we can assemble the complete framework for hash-based pattern matching:

Algorithm skeleton:

1. Preprocessing (O(m)):

   • Compute pattern_hash = hash(pattern)
   • Compute bᵐ⁻¹ mod q for use in rolling updates
   • Compute text_hash = hash(text[0:m]) for first window

2. Matching (O(n)):

   • Compare text_hash with pattern_hash
   • If equal: verify with character-by-character comparison
   • Roll the window: update text_hash using O(1) formula
   • Repeat until end of text

This gives O(n+m) expected time. We'll analyze this precisely in a later page, including understanding when and why the worst case can degrade.

Key observations from this framework:

1. Hash comparisons dominate: We perform n-m+1 hash comparisons, each O(1)
2. Character comparisons are rare: Only when hashes match do we verify
3. The rolling update is essential: Without it, computing each window's hash would take O(m)
4. Modular arithmetic is crucial: Without mod, hash values would grow exponentially large

The next page explores the rolling hash technique in complete detail, including handling negative modular values and optimizing the implementation.

We've established the foundational concepts that make Rabin-Karp possible. Let's consolidate what we've learned:

What's next:

In the next page, we'll dive deep into the rolling hash technique—the mathematical machinery that makes O(1) hash updates possible. We'll explore the precise formulas, handle edge cases with modular arithmetic, and build a production-ready implementation.