Rabin-Karp String Matching Algorithm, Explained

Quick Answer

Rabin-Karp finds a pattern inside a text by comparing hash values instead of comparing characters one by one. It hashes the pattern once, then slides a rolling hash across the text so each new window's hash costs O(1) to compute from the previous one. When two hashes match, it does one quick character-by-character check to rule out a hash collision before reporting a real match.

The problem: finding a pattern without re-reading everything

Say you're searching a 50,000-character log file for the substring "connection refused". The obvious approach, the naive one, is to try every starting position in the text and check character by character whether the pattern matches there. That's O(n*m) in the worst case, where n is the text length and m is the pattern length. For most everyday strings that's fine. But when you're searching for many patterns at once, or searching repeatedly inside a very large text (think plagiarism detectors scanning millions of documents, or a DNA sequence search across a genome), re-comparing characters every single time starts to hurt.

Richard Karp and Michael Rabin published a different idea in 1987: instead of asking "do these two substrings match character by character", ask "do these two substrings have the same hash value". If you can compute a hash for a window of text in O(1) time as that window slides forward by one character, you can scan the whole text in O(n) time on average, only falling back to an O(m) character check on the rare occasions the hashes actually collide.

This is the core trick behind Rabin-Karp: it trades an exact character comparison for a cheap numeric comparison, and only pays the exact-comparison cost when the cheap check says "maybe".

Where this actually gets used

You'll rarely reach for Rabin-Karp to find a single short pattern in a single short string, plain string search or the built-in str.find() in your language already does that well. Rabin-Karp earns its keep in three specific situations: multi-pattern search against a single text (hash a whole dictionary of patterns and check text windows against the set), approximate duplicate detection (hash rolling windows of documents and compare hash sets to find overlapping passages), and bioinformatics-style scanning where the alphabet is tiny (A, C, G, T) and the text is enormous.

It's also one of those algorithms interviewers like asking about specifically because it tests whether you understand hashing trade-offs, not just whether you memorised a pointer-chasing trick.

The rolling hash: the one trick that makes this fast

Treat a string of characters as digits of a number in some base (256 works well since it covers every byte value). The string "cat" in base 256 is roughly ord('c') * 256^2 + ord('a') * 256^1 + ord('t') * 256^0. That's a huge number for anything longer than a few characters, so in practice you compute it modulo a large prime (or a large number close to one) to keep it inside normal integer ranges, while still getting a value that's unlikely to collide between different strings.

The magic part is updating this hash as the window slides. Suppose you know the hash of text[i : i+m] and you want the hash of text[i+1 : i+m+1], one character to the right. You don't recompute from scratch. You:

• Subtract the contribution of the character leaving the window (text[i]), which sat at the most significant digit position, so you multiply its value by base^(m-1) first.
• Multiply the remaining hash by base to shift every digit one place over.
• Add the contribution of the new character entering the window (text[i+m]).

All of this happens modulo your chosen modulus, so every step stays O(1) regardless of how long the pattern is. That's the entire trick: the hash for the next window is derived from the hash of the current window in constant time, which is why the whole scan runs in O(n) rather than O(n*m).

One subtlety worth internalising: this hash function is called a "polynomial rolling hash" precisely because each character acts like a coefficient of a polynomial evaluated at base. It's the same underlying idea used in rolling checksums elsewhere in computing, just applied to exact substring matching here.

The algorithm, step by step

Putting the rolling hash to work for pattern search looks like this:

1. Compute the hash of the pattern once, up front.
2. Compute the hash of the first window of the text (the first m characters).
3. Compare the two hashes. If they match, do a direct character-by-character check of that window against the pattern. If that check also passes, record a real match.
4. Slide the window forward by one character using the rolling-hash update, and repeat step 3 until you reach the end of the text.

Two details decide whether an implementation is correct or subtly broken:

1. You must verify every hash match

A hash match is a strong hint, not proof. Two different strings can, by bad luck, produce the same hash value, that's called a collision. Skipping the verification step and trusting the hash blindly is the single most common Rabin-Karp bug, and it's the kind of bug that passes every test you happen to try and then quietly reports a false match in production on some input you didn't think to test. The section below shows this failing for real with a deliberately small modulus.

2. Negative numbers after the subtraction step

In most languages, subtracting a larger number from a smaller one inside a modulus calculation can give you a negative intermediate result before the final modulo wraps it back into range. Python's % operator actually handles this gracefully (it always returns a non-negative result for a positive modulus), but if you're porting this to C, Java, or JavaScript, you need an explicit (x % mod + mod) % mod guard, or you will get silently wrong answers that look like an off-by-one bug but are actually a sign bug.

Python implementation, and a real run against five test cases

Here's a complete, runnable implementation. It uses base 256 (enough for any byte value) and a modulus just under 2^30 to keep collisions rare without needing big-integer arithmetic to slow things down:

def rabin_karp(text, pattern, base=256, mod=1_000_000_007):
    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:
            # verify to guard against a hash collision (spurious hit)
            if text[i:i+m] == pattern:
                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

I ran this against five hand-picked cases, including an empty string and a pattern with no match at all, and compared every result against a plain, trusted, naive search:

text='abxabcabcaby'            pattern='abcaby'   naive=[6] rk=[6] [OK]
text='aaaaaaaaaa'              pattern='aaa'      naive=[0, 1, 2, 3, 4, 5, 6, 7] rk=[0, 1, 2, 3, 4, 5, 6, 7] [OK]
text='hello world'             pattern='xyz'      naive=[] rk=[] [OK]
text=''                        pattern='a'        naive=[] rk=[] [OK]
text='gatcgatcgatc'            pattern='gatc'     naive=[0, 4, 8] rk=[0, 4, 8] [OK]

Every case lines up with the naive search. The all-a case is worth noting specifically, it has eight overlapping matches of "aaa" inside "aaaaaaaaaa", and the rolling hash correctly finds every overlapping position rather than skipping past matches the way some naive implementations accidentally do when they advance by the pattern length instead of by one character.

A couple of details in this implementation are worth calling out explicitly. The modulus 1_000_000_007 is a commonly used large prime in competitive programming specifically because it's just under 2^30, comfortably inside the range where multiplying by a small base like 256 doesn't overflow ordinary 64-bit integer arithmetic in languages that have fixed-width integers (Python's own integers are arbitrary precision, so this isn't strictly necessary here, but it matters the moment you port this to C++, Java, or Go). The empty-string case, pattern "a" against text "", is handled by the explicit if m == 0 or m > n: return [] guard at the top of the function, without it, the loop bounds would quietly produce a negative range and either throw or silently iterate zero times depending on the language, which is worth testing explicitly rather than assuming it just works.

Why you must verify after a hash match, shown with a real collision

To make the collision risk concrete instead of theoretical, I reran the same rolling-hash logic but swapped the modulus from roughly a billion down to 101, a deliberately tiny prime that makes collisions likely on purpose. Searching for "bat" inside "the cat sat on the mat while a bat flew by the rat":

Small-modulus run (shows why verification matters):
true positions: [31]
raw hash-equal candidates (mod=101): [31, 40]

The true occurrence of "bat" is at index 31. But the tiny-modulus hash also flags index 40 as a candidate, that's actually where "rat" appears, and with only 101 possible hash values, "bat" and "rat" happen to land on the same bucket. An implementation that trusted the hash and skipped the character check would report a match at index 40 that doesn't exist in the text.

This is exactly why the algorithm as originally described, and every correct implementation since, treats a hash match as a candidate, never as a confirmed result. With a properly sized modulus (close to 2^30 or larger, as in the main implementation above), collisions become rare enough that the verification step costs almost nothing in practice, it fires occasionally, does an O(m) check, and moves on, while still being mathematically guaranteed to never report a false positive.

There's a sharper version of this lesson worth knowing if you ever ship Rabin-Karp-style hashing in a security-sensitive context: choosing a small or predictable modulus isn't just a correctness risk, it's an exploitable one. In 2011, several popular web frameworks were found vulnerable to "hash-flooding" denial-of-service attacks, where an attacker who could predict a hash function's internal parameters crafted thousands of inputs that all collided into the same bucket, turning an expected fast lookup into a slow linear scan across the board. The fix in that case, and the lesson here, is the same: never trust a hash match as proof of equality when the hash space is small enough, or predictable enough, for an adversary to engineer collisions on purpose. A modulus near 2^30 or larger, with no pattern an attacker could exploit, keeps accidental collisions rare and deliberate ones impractical for the input sizes this algorithm is normally used at.

Time and space complexity, honestly stated

Average case: O(n + m), where n is the text length and m is the pattern length. Each window costs O(1) to hash thanks to the rolling update, and verification only fires on genuine hash matches, which are rare with a good modulus.

Worst case: O(n*m). If your modulus is small, or an adversary crafts input specifically to cause repeated collisions, every window could trigger a full O(m) verification, degrading to the same bound as naive search. This is a real, known weakness, not a hypothetical one: Rabin-Karp's worst case is only as good as naive search, and a poorly chosen modulus is the usual cause.

Space complexity is O(1) beyond the input itself, you only ever store a handful of integers (the pattern hash, the current window hash, and the precomputed base^(m-1) term), regardless of how long the text is.

Where it genuinely wins over alternatives: searching for many patterns against one text (hash every pattern into a set, then slide one window across the text checking set membership, which turns an O(k*n*m) multi-pattern naive search into roughly O(n + sum of pattern lengths)), and 2D pattern matching (rolling hashes extend naturally to grids, which is harder to do cleanly with pointer-based string algorithms).

To put the worst case in concrete terms: imagine searching a 1,000,000-character text for a 20-character pattern using a modulus of just 7. With only seven possible hash buckets, a huge fraction of the roughly 1,000,000 candidate windows will hash into the same bucket as the pattern purely by chance, forcing a full 20-character verification at nearly every position, which is exactly the O(n*m) naive-search bound the rolling hash was supposed to help you avoid. This is why production implementations almost always use a modulus in the billions, or avoid a fixed single modulus entirely by using two independent hashes and requiring both to match, which drives the probability of an accidental double-collision down to effectively zero for any realistic input size.

Rabin-Karp vs KMP vs the Z-algorithm

These three solve the same basic problem (find a pattern inside a text) but earn their speed in different ways, and picking between them in an interview setting is as much about explaining the trade-off as writing the code:

KMP and the Z-algorithm both guarantee linear time no matter what, which is why textbooks often present them as the "correct" answer to single-pattern search. Rabin-Karp's average case is just as good, but its worst case is genuinely worse, so it's not the tool to reach for when you need a hard guarantee against adversarial input. Where Rabin-Karp pulls ahead is exactly the situations where you're not matching one fixed pattern: hashing scales naturally to sets of patterns and to higher-dimensional matching in a way that pointer-based failure functions don't.

A practical decision rule that holds up well in both interviews and real code reviews: if you're matching one pattern against one text and need a hard guarantee regardless of input, reach for KMP or the Z-algorithm. If you're matching many patterns against one text, or building something like a duplicate-detection or plagiarism tool where you'll be comparing rolling windows across many documents, Rabin-Karp's hashing approach generalizes more naturally and usually ends up simpler to extend, even though its single-pattern worst case is technically weaker. Priodemy's companion article on the Z-algorithm covers the guaranteed-linear-time alternative in the same depth, for cases where a hard worst-case bound is what you actually need.

Frequently Asked Questions