Rabin-Karp Algorithm

Analogy categoryAnalogies

Introduction

The Rabin-Karp algorithm finds occurrences of a pattern in a text by comparing hash values of substrings instead of comparing characters directly at every position. It computes a hash of the pattern and a hash of each length-m window of the text, using a rolling hash that can be updated in O(1) when the window slides by one character. When hashes match, it verifies with a direct character comparison to guard against hash collisions.

🏏

Cricket analogy: Instead of checking every ball-by-ball sequence character by character for a repeated bowling pattern, Rabin-Karp computes a quick hash 'signature' for each 6-ball window and only does a detailed replay check when signatures match, guarding against a coincidental hash collision.

Algorithm/Syntax

python

def rabin_karp_search(text: str, pattern: str, base: int = 256, mod: int = 1_000_000_007) -> list[int]:
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []

    high_order = pow(base, m - 1, mod)
    pattern_hash = 0
    window_hash = 0
    for i in range(m):
        pattern_hash = (pattern_hash * base + ord(pattern[i])) % mod
        window_hash = (window_hash * base + ord(text[i])) % mod

    matches = []
    for i in range(n - m + 1):
        if window_hash == pattern_hash:
            if text[i:i + m] == pattern:  # verify to rule out collisions
                matches.append(i)
        if i < n - m:
            window_hash = (window_hash - ord(text[i]) * high_order) % mod
            window_hash = (window_hash * base + ord(text[i + m])) % mod
            window_hash %= mod
    return matches

Explanation

Each substring of length m is treated as a number in a given base (e.g. 256 for byte values), reduced modulo a large prime to keep values bounded. The rolling hash update removes the contribution of the outgoing character (text[i] * base^(m-1)) and adds the incoming character (text[i+m]), all in O(1), rather than recomputing the hash of the whole window from scratch. Because different substrings can occasionally hash to the same value (a collision), Rabin-Karp always verifies a hash match with an explicit character-by-character comparison before accepting it as a true match; this keeps the algorithm correct while the hashing keeps it fast on average.

🏏

Cricket analogy: Treating each 6-ball window as a number in a numeral system and reducing it modulo a large prime keeps the hash bounded; sliding to the next window just removes the outgoing ball's contribution and adds the incoming ball's, an O(1) rolling update instead of re-hashing all 6 balls from scratch.

Example

python

text = "abxabcabcaby"
pattern = "abc"
result = rabin_karp_search(text, pattern)
print("Matches at indices:", result)  # [4, 7]

# Trace (base=256, small mod for illustration only):
# window 'abx' -> hash H1
# window 'abc' (shift by 1) -> hash updated in O(1) using rolling formula
# hash of 'abc' pattern matches window at index 4 and index 7 -> verified equal -> recorded

Complexity

Average and best case time is O(n+m): O(m) to compute the initial pattern and window hashes, and O(n-m) rolling updates each costing O(1), plus verification that is cheap on average because collisions are rare with a good modulus. Worst case, if many spurious hash collisions occur (or an adversarial input/modulus is chosen), each verification can cost O(m), giving O(n*m) worst case. Using a large prime modulus and, optionally, double hashing, makes worst-case collisions extremely unlikely in practice. Space is O(1) beyond the input.

🏏

Cricket analogy: On average, scanning a full season's ball-by-ball log for a specific bowling pattern of length m takes O(n+m) with Rabin-Karp's rolling hash, but an adversarial sequence causing many hash collisions could degrade to O(n*m); using a large prime modulus, like choosing a bigger boundary rope, makes that worst case rare, and needs no extra scoreboard space beyond the log.

Key Takeaways

Rabin-Karp compares hash values of substrings instead of raw characters, updating the hash in O(1) as the window slides (rolling hash).
A hash match must always be verified with a direct string comparison to rule out collisions.
Average/best-case time is O(n+m); worst case degrades to O(n*m) under heavy hash collisions.
It generalizes well to searching for multiple patterns simultaneously by comparing against a set of pattern hashes.

Practice what you learned

1. What is the key data structure/technique that makes Rabin-Karp efficient?

2. Why does Rabin-Karp verify a match with a direct character comparison even after the hashes match?

3. What is the average-case time complexity of Rabin-Karp?

4. In the rolling hash update, what must be subtracted out when the window slides forward by one character?

5. What causes Rabin-Karp's worst-case time to degrade to O(n*m)?

Was this page helpful?

Naive String Matching and KMP

Longest Palindromic Substring

Topics covered

#Python#AlgorithmsStudyNotes#Algorithms#RabinKarpAlgorithm#Rabin#Karp#Algorithm#Syntax#StudyNotes#SkillVeris