Oh My Algorithm
Algorithm Guidecomplexity: Avg O(n + m)

Rabin-Karp

A string search that compares hash values of the pattern and text windows. A rolling hash updates the window hash in O(1), and it only checks the actual characters when the hashes match — handy for multi-pattern search.

01Rabin-Karp

Rabin-Karp starts. It compares the 'hash values' of the pattern and text windows to filter candidates fast.

Precompute the hash of pattern 'CAB' (say it's 17).

Window [0,2] 'ABA' hashes to 31. It differs from 17, so skip it without even looking at the actual chars.

A rolling hash updates the next window [1,3] 'BAC' in O(1) = 22. Still different.

Window [2,4] 'ACA' hash = 19. Different again.

Window [3,5] 'CAB' hash = 17. It matches the pattern hash! Now verify the actual chars.

The chars 'CAB' exactly equal the pattern (not a hash collision). Found at index 3!

A rolling hash updates the window hash in O(1), matching in O(n+m) on average.

text
A
B
A
C
A
B
C
A
B
pattern
1 / 8

02 Understand It Simply

For Everyone
🔑How It Works

Compares the hash of the pattern against the hash of each window, checking actual characters only on a match. Sliding the window updates the hash instead of recomputing it.

💡In Plain Words

Compares the hash of the pattern and a text window, checking actual characters only when they match.

A rolling hash updates the window hash in O(1) to sweep fast.

📍Where It's Used
  • –Plagiarism/duplicate-document checks
  • –multi-pattern search

03 Python Implementation

A clean, readable reference implementation of the core logic of Rabin-Karp.

core_implementation.py
def rabin_karp(text, pattern, base=256, mod=1_000_000_007):
    n, m = len(text), len(pattern)
    if m > n:
        return -1
    high = pow(base, m - 1, mod)
    p_hash = t_hash = 0
    for i in range(m):
        p_hash = (p_hash * base + ord(pattern[i])) % mod
        t_hash = (t_hash * base + ord(text[i])) % mod
    for i in range(n - m + 1):
        if p_hash == t_hash and text[i:i + m] == pattern:
            return i
        if i < n - m:
            t_hash = ((t_hash - ord(text[i]) * high) * base
                      + ord(text[i + m])) % mod
    return -1

04 Frequently Asked Questions

FAQ
What is Rabin-Karp?+

A string search that compares hash values of the pattern and text windows. A rolling hash updates the window hash in O(1), and it only checks the actual characters when the hashes match — handy for multi-pattern search.

What is the time complexity of Rabin-Karp?+

The time complexity of Rabin-Karp is Avg O(n + m). Follow the step-by-step visualization to see exactly why.

Where is Rabin-Karp used?+

Plagiarism/duplicate-document checks, multi-pattern search.

What's a simple analogy for Rabin-Karp?+

Compares the hash of the pattern against the hash of each window, checking actual characters only on a match. Sliding the window updates the hash instead of recomputing it.

→ Strings — see allRelated
🔤KMP (Knuth-Morris-Pratt)
O(n + m)
🔤Boyer-Moore
Best O(n / m)