Rabin-Karp: Searching With Rolling Fingerprints

Most string searches work by comparing letters. Rabin-Karp takes a different road: it boils every chunk of text down to a single number, a fingerprint, and compares the numbers instead. The clever part is that the fingerprint of the next chunk can be worked out from the previous one in a couple of arithmetic steps, so sliding along a million-letter document never requires re-reading anything. That small trick turns out to be behind plagiarism checkers, backup tools that avoid storing duplicate data, and filters that scan for thousands of forbidden words at once. This guide builds the idea from scratch, using small numbers you can follow by hand, and backs every claim with code I actually ran.

A different way to look for a needle

Imagine you are a security guard checking faces against a wanted poster. You could memorise the poster and study every visitor’s eyes, nose, jaw and hairline one feature at a time. Or you could take a quick glance at each visitor and ask a much cheaper question first: does this person even roughly resemble the photo? Ninety-nine visitors fail that glance instantly. For the rare one who passes, then you do the careful feature-by-feature check.

That is Rabin-Karp in one paragraph. The glance is a hash, a number computed from the text. The careful check is the ordinary letter-by-letter comparison. The algorithm is named after its two inventors, the computer scientists Michael Rabin and Richard Karp, who published it in 1987, and its central idea has aged remarkably well.

Step one: turn a string into a number

Computers love numbers and are slow at comparing long strings, so let us convert. The easiest example uses digits, because a string of digits already is a number. The text “31415” becomes the number thirty-one thousand four hundred fifteen. Two strings of digits are equal exactly when their numbers are equal, and comparing two numbers is one operation no matter how many digits are inside.

That already sounds like a win, but there is a catch. With a needle 50 letters long, the number can be enormous, far too big to handle in one machine word. The fix is to keep only the remainder after dividing by some fixed number, the modulus. In my first example I use 13, which is tiny on purpose so that you can do the arithmetic in your head. The number 31415 divided by 13 leaves a remainder of 7. So the fingerprint of “31415” is 7.

Notice what we gave up. Many different strings leave the same remainder: 7 is also the fingerprint of other five-digit numbers. We will deal with that in a moment, because it is the whole reason the algorithm has a verification step. First, the clever bit.

Step two: the rolling update

To search a long text, you need the fingerprint of every window of five consecutive digits. Computing each one from scratch would cost five operations per window, which is no better than comparing the digits directly. The rolling hash avoids that by reusing the previous answer.

Take the window “31415” and slide one place to the right so that it becomes “14152”. Three things happened: the leading 3 fell off the left, every remaining digit shifted one place up, and a new 2 arrived at the right. In arithmetic terms:

Check it with real numbers: (31415 − 3 × 10000) × 10 + 2 = 1415 × 10 + 2 = 14152. Correct, and it took three arithmetic operations, regardless of how long the window is.

The picture shows the same update done modulo 13, which is what the program really does. The weight of the leading digit, 10⁴, becomes 3 mod 13. Starting from the fingerprint 7, you compute (7 − 3 × 3) × 10 + 2 = −18. That is negative, so you add 13 until it is non-negative, giving 8. And 14152 divided by 13 does leave a remainder of 8. The shortcut and the long way agree.

Negative intermediate results deserve a warning. Python’s remainder operator always returns a non-negative result for a positive modulus, so the code above just works. In C, C++ and Java, the remainder of a negative number can be negative, which silently breaks the fingerprints. If you write this in one of those languages, add the modulus back before taking the remainder.

Walking through a whole search

Here is a complete search on digits, with the numbers printed so nothing is hidden. The haystack is 2359023141526739921, the needle is 31415, and the modulus is 13. For every window the program shows its fingerprint and whether it equals the needle’s fingerprint of 7. It also asserts, on every step, that the rolling update gives the same answer as computing the fingerprint from scratch.

# Textbook-style walk-through with digits so you can follow the arithmetic.
text, pat, mod = "2359023141526739921", "31415", 13
m = len(pat)
target = int(pat) % mod
print(f"pattern {pat} -> {int(pat)} mod {mod} = {target}")
print()
print("shift  window   hash   verdict")
high = 10 ** (m - 1) % mod
h = int(text[:m]) % mod
for s in range(len(text) - m + 1):
    window = text[s:s + m]
    assert h == int(window) % mod            # rolling value equals the direct value
    verdict = ""
    if h == target:
        verdict = "REAL match" if window == pat else "spurious hit (same hash, different text)"
    print(f"{s:>5}  {window}  {h:>5}   {verdict}")
    if s < len(text) - m:
        h = ((h - int(text[s]) * high) * 10 + int(text[s + m])) % mod

Output:

pattern 31415 -> 31415 mod 13 = 7

shift  window   hash   verdict
    0  23590      8   
    1  35902      9   
    2  59023      3   
    3  90231     11   
    4  02314      0   
    5  23141      1   
    6  31415      7   REAL match
    7  14152      8   
    8  41526      4   
    9  15267      5   
   10  52673     10   
   11  26739     11   
   12  67399      7   spurious hit (same hash, different text)
   13  73992      9   
   14  39921     11

Read down the hash column. At shift 6 the window is 31415 and the fingerprint is 7, the same as the needle: a real match. But look at shift 12. The window is 67399, which is a completely different string, and yet its fingerprint is also 7. This is called a spurious hit or false positive. If the algorithm trusted fingerprints alone, it would report a match there that does not exist.

That is why the verification step is not optional. Whenever fingerprints agree, Rabin-Karp compares the real letters. In this example it would check the window at shift 6, confirm it, check the window at shift 12, reject it, and ignore the other thirteen windows entirely. Two letter-by-letter comparisons instead of fifteen. On a longer text with a longer needle, the saving grows.

From digits to letters

Letters are not digits, but every character has a numeric code, such as 65 for A and 97 for a. So we treat a string as a number written in base 256 (a base large enough to cover ordinary byte values), where each character is one digit. The text “ABC” becomes 65 × 256² + 66 × 256 + 67 = 4,276,803. Everything we did with base 10 works with base 256, as long as we replace 10 by 256 in the update formula.

Here is the complete function, followed by a check of the rolling update on a small example and a tiny search:

def rabin_karp(text, pat, base=256, mod=1_000_000_007):
    """Return (match positions, hash hits that needed checking, false alarms)."""
    n, m = len(text), len(pat)
    if m == 0 or m > n:
        return [], 0, 0
    high = pow(base, m - 1, mod)             # weight of the leading character
    hp = ht = 0
    for i in range(m):                       # fingerprints of pattern and first window
        hp = (hp * base + ord(pat[i])) % mod
        ht = (ht * base + ord(text[i])) % mod
    hits, checks, false_alarms = [], 0, 0
    for s in range(n - m + 1):
        if ht == hp:                         # fingerprints agree: now compare letters
            checks += 1
            if text[s:s + m] == pat:
                hits.append(s)
            else:
                false_alarms += 1
        if s < n - m:                        # slide the window by one letter
            ht = ((ht - ord(text[s]) * high) * base + ord(text[s + m])) % mod
    return hits, checks, false_alarms


if __name__ == "__main__":
    base, mod = 256, 1_000_000_007
    h = lambda w: sum(ord(c) * base ** (len(w) - 1 - i) for i, c in enumerate(w)) % mod
    old = h("ABC")
    new = ((old - ord("A") * pow(base, 2, mod)) * base + ord("D")) % mod
    print("hash(ABC)                  =", old)
    print("slide: drop A, add D       =", new)
    print("hash(BCD) computed afresh  =", h("BCD"))
    print("rolling update is correct  =", new == h("BCD"))
    print()
    print(rabin_karp("the quick brown fox jumps over the lazy dog", "brown"))

Output:

hash(ABC)                  = 4276803
slide: drop A, add D       = 4342596
hash(BCD) computed afresh  = 4342596
rolling update is correct  = True

([10], 1, 0)

The top four lines confirm the rolling update: the hash of “ABC” is 4,276,803, and dropping the A and adding a D gives 4,342,596, exactly the same as computing “BCD” from scratch. The last line is the search result for “brown” in “the quick brown fox jumps over the lazy dog”: one match at position 10, one hash hit that needed checking, and zero false alarms.

The function returns three numbers: the match positions, how many fingerprint agreements triggered a letter check, and how many of those checks turned out to be false alarms. That last number is the interesting one, because it is where the algorithm can go wrong.

Collisions and the choice of modulus

A fingerprint collision happens when two different strings produce the same number. They cannot be avoided entirely, since there are far more possible strings than possible remainders. What you control is how often they happen, and the main lever is the size of the modulus. If the fingerprints behave like random numbers, the chance that a wrong window collides with the needle is about one in the modulus.

I tested that on 200,000 random letters with an 8-letter needle that does not occur, using three moduli:

import random
from rk import rabin_karp

random.seed(5)
text = "".join(random.choice("abcdefghijklmnopqrstuvwxyz") for _ in range(200000))
pat = "qzjxkvwp"
print(f"{len(text) - len(pat) + 1:,} windows, pattern of {len(pat)} letters")
print(f"{'modulus':>15}{'hash hits':>11}{'false alarms':>14}")
for mod in (101, 10007, 1_000_000_007):
    hits, checks, bad = rabin_karp(text, pat, 256, mod)
    print(f"{mod:>15,}{checks:>11}{bad:>14}   real matches: {len(hits)}")

Output:

199,993 windows, pattern of 8 letters
        modulus  hash hits  false alarms
            101       2041          2041   real matches: 0
         10,007         19            19   real matches: 0
  1,000,000,007          0             0   real matches: 0

With a tiny modulus of 101, about 1 window in 100 was a false alarm: 2,041 wasted letter checks across nearly 200,000 windows. With 10,007 the number dropped to 19, and with a modulus around a billion it was zero. The pattern matches the “one in the modulus” rule almost perfectly.

So why not always use a gigantic modulus? Because arithmetic on huge numbers costs more, and in languages with fixed-width integers a product can overflow. A common compromise is a prime modulus around a billion, with care that intermediate products fit in 64 bits. Python hides this problem because its integers grow as needed, which is also why Python code like mine runs slower than the same idea in C.

Why a prime, and why random?

Prime moduli spread remainders more evenly, which reduces patterned collisions. There is also a security angle. If a program uses a fixed, publicly known base and modulus, a hostile user can craft inputs that collide on purpose, forcing many false alarms and slowing the search to a crawl. Careful implementations choose the base, or the modulus, at random when the program starts. This is a real concern whenever the text comes from outside.

How fast is it, really?

The running time is about n + m in the typical case, where n is the length of the haystack and m the length of the needle. Computing the first two fingerprints costs about m steps, and each of the n slides costs a constant amount. Verification only happens on fingerprint hits, which are mostly real matches or rare false alarms, so it adds little.

The worst case is n × m. It happens when nearly every window collides, for example with a terrible modulus or an adversarial input, so that you verify almost every position. With a well-chosen, randomised modulus that is extremely unlikely. This is the reverse of the trade-off in KMP, which guarantees linear time on every input but is not always the fastest on friendly text. Rabin-Karp is expected linear time with a small, controllable risk.

For a single short needle, honestly, Rabin-Karp is not the champion. The fingerprint arithmetic costs more per step than comparing a single letter, and skip-ahead methods or your language’s built-in search beat it. Its real strength lies elsewhere.

The superpower: many needles at once

Suppose you have 2,000 banned words, or a database of known phrases, and one document to scan. With one-needle-at-a-time methods you repeat the entire search 2,000 times. Rabin-Karp lets you do it in a single pass. Compute the fingerprint of every needle once and put them in a set. Then slide the window over the document one time, and at each position ask a single question: is this window’s fingerprint in the set? A set lookup takes constant time, so the cost of one pass hardly depends on how many needles you have.

The one restriction is that this simple version needs all the needles to be the same length, so that one window size fits them all. For different lengths, you run one pass for each distinct length.

I measured it with 200 needles of 8 letters, five of them planted in a 200,000-letter text:

import random, time
from rk import rabin_karp
from kmp import kmp_search

random.seed(3)
letters = "abcdefghijklmnopqrstuvwxyz"
text = "".join(random.choice(letters) for _ in range(200000))
patterns = ["".join(random.choice(letters) for _ in range(8)) for _ in range(195)]
patterns += [text[i:i + 8] for i in (1000, 50000, 90000, 150000, 199000)]   # five planted
M = 8; BASE = 256; MOD = (1 << 61) - 1

def multi_rabin_karp(text, patterns):
    """One pass over the text, any number of equal-length patterns."""
    table = {}
    for p in patterns:
        hp = 0
        for ch in p:
            hp = (hp * BASE + ord(ch)) % MOD
        table.setdefault(hp, []).append(p)
    high = pow(BASE, M - 1, MOD)
    ht = 0
    for ch in text[:M]:
        ht = (ht * BASE + ord(ch)) % MOD
    found = {}
    for s in range(len(text) - M + 1):
        if ht in table:
            for p in table[ht]:
                if text[s:s + M] == p:
                    found.setdefault(p, []).append(s)
        if s < len(text) - M:
            ht = ((ht - ord(text[s]) * high) * BASE + ord(text[s + M])) % MOD
    return found

if __name__ == "__main__":
    def timed(fn):
        t = time.perf_counter(); r = fn(); return r, (time.perf_counter() - t) * 1000

    a, ta = timed(lambda: multi_rabin_karp(text, patterns))
    b, tb = timed(lambda: {p: h for p in patterns for h in [kmp_search(text, p)[0]] if h})
    d, td = timed(lambda: {p: True for p in patterns if text.find(p) >= 0})
    print(f"{len(patterns)} patterns, {len(text):,} letters of text")
    print(f"patterns found by Rabin-Karp : {len(a)}")
    print(f"patterns found by KMP loop   : {len(b)}")
    print(f"patterns found by str.find   : {len(d)}")
    print()
    print(f"one Rabin-Karp pass (pure Python) : {ta:8.1f} ms")
    print(f"one KMP run per pattern (Python)  : {tb:8.1f} ms")
    print(f"str.find per pattern (C built-in) : {td:8.1f} ms")

Output:

200 patterns, 200,000 letters of text
patterns found by Rabin-Karp : 5
patterns found by KMP loop   : 5
patterns found by str.find   : 5

one Rabin-Karp pass (pure Python) :    144.5 ms
one KMP run per pattern (Python)  :   4373.2 ms
str.find per pattern (C built-in) :     26.8 ms

All three methods found the same five planted needles. The single Rabin-Karp pass took roughly 70 to 150 milliseconds across my runs, depending on how busy the machine was. Running my Python KMP once per needle took about four seconds, roughly thirty to sixty times slower. But notice the last line: Python’s built-in find, written in C, finished the 200 searches in under 30 milliseconds, and beat my pure Python Rabin-Karp. The language matters as much as the algorithm.

The real question is what happens as the number of needles grows. So I scaled it up:

import random, time
from multi import multi_rabin_karp, text, letters

random.seed(11)
print(f"{'patterns':>9}{'Rabin-Karp one pass':>22}{'str.find per pattern':>23}")
for k in (200, 2000, 20000):
    pats = ["".join(random.choice(letters) for _ in range(8)) for _ in range(k)]
    t = time.perf_counter(); multi_rabin_karp(text, pats); a = (time.perf_counter() - t) * 1000
    t = time.perf_counter(); [text.find(p) for p in pats]; b = (time.perf_counter() - t) * 1000
    print(f"{k:>9,}{a:>19.1f} ms{b:>20.1f} ms")

Output:

 patterns   Rabin-Karp one pass   str.find per pattern
      200              119.1 ms                31.5 ms
    2,000              125.6 ms               277.1 ms
   20,000              107.5 ms              2757.4 ms

This is the picture that justifies the method. The per-needle approach grows in a straight line: ten times more needles took about ten times longer, reaching 2.7 seconds for 20,000. The single Rabin-Karp pass stayed roughly flat around a tenth of a second, because walking through the text dominates and each lookup costs the same. Somewhere between 200 and 2,000 needles, the crossover happens even against a C built-in, and beyond it the gap keeps widening.

Fingerprinting documents: a plagiarism detector in 40 lines

Here is where the rolling hash really surprised me early in my career. Instead of searching for a known needle, you can fingerprint every window of a document and keep the whole set of fingerprints. Two documents that share long passages will share many fingerprints. Two unrelated documents will share almost none.

The recipe: lowercase the text, strip everything except letters so that punctuation and spacing tricks do not matter, then compute the rolling hash of every 12-letter window. The fingerprint set is a compact summary of the document. Comparing two summaries means intersecting two sets.

import re

BASE, MOD, K = 256, (1 << 61) - 1, 12

def fingerprints(text, k=K):
    """Set of rolling hashes of every k-letter window (letters only, lower-case)."""
    t = re.sub(r"[^a-z]", "", text.lower())
    high = pow(BASE, k - 1, MOD)
    h = 0
    for ch in t[:k]:
        h = (h * BASE + ord(ch)) % MOD
    out = {h}
    for s in range(len(t) - k):
        h = ((h - ord(t[s]) * high) * BASE + ord(t[s + k])) % MOD
        out.add(h)
    return out

original = ("Rolling hashes let a program fingerprint every window of a document in constant time, "
            "which is why plagiarism checkers can compare thousands of essays quickly.")
edited   = ("Rolling hashes let a program fingerprint every window of a document in constant time, "
            "which is why copy detectors can compare thousands of essays very quickly.")
unrelated = ("The monsoon reached the hills early this year, and the apple orchards along the river "
             "were heavy with blossom by the middle of April.")

base_fp = fingerprints(original)
print(f"original has {len(base_fp)} fingerprints")
for name, doc in (("light edit", edited), ("unrelated", unrelated), ("exact copy", original)):
    shared = len(base_fp & fingerprints(doc))
    print(f"{name:<11}: {shared:>3} shared  ->  {100 * shared / len(base_fp):5.1f}% of the original")

Output:

original has 122 fingerprints
light edit :  88 shared  ->   72.1% of the original
unrelated  :   0 shared  ->    0.0% of the original
exact copy : 122 shared  ->  100.0% of the original

The original sentence produced 122 fingerprints. A lightly edited copy, where I swapped two phrases, still shared 88 of them, 72 percent. An unrelated sentence about apple orchards shared none. An exact copy shared all 122. Notice that the edit did not destroy the comparison: because each fingerprint covers only 12 letters, the untouched stretches of the sentence still match even after the changed words break the windows around them.

Real systems build on exactly this. They pick the window length carefully, since too short gives false similarity from common phrases and too long misses lightly reworded copying. Some, such as the approach behind Stanford’s well-known MOSS code-similarity tool, keep only a well-chosen sample of the fingerprints so that the summary stays small. The core machinery is still the rolling hash.

All the methods side by side

Where rolling fingerprints are used

You may never write Rabin-Karp for a Ctrl+F box, but its idea runs through systems you use daily. Click through five situations and notice what they share: the data is big, the comparison is repeated, and a cheap fingerprint filters out nearly everything before any expensive work.

Which approach should you choose?

Here is the short checklist I use. The first question settles most real-world cases.

Common mistakes and how to avoid them

• Trusting the fingerprint without verifying. A hash match only means “probably equal”. Always compare the real letters before reporting a hit, as the spurious match at shift 12 showed.
• Choosing a tiny modulus. A modulus of 101 gave about one false alarm per hundred windows in my test. Use a large prime.
• Forgetting the negative remainder. After subtracting the outgoing letter, the value can be negative. In C, C++ and Java, add the modulus before taking the remainder.
• Getting the leading weight wrong. The weight must be base to the power m − 1, taken modulo the modulus. A wrong power gives fingerprints that look plausible but never match.
• Letting integers overflow. With a modulus near a billion and a base of 256, one product fits in 64 bits. Choose both values together.
• Using a predictable base and modulus on untrusted text. Attackers can craft collisions. Randomise one of them when the program starts.
• Mixing pattern lengths in the multi-needle version. One window length checks one needle length. Group the needles by length.
• Reaching for it when the built-in would do. For a single search in ordinary code, the language’s own find is simpler and faster.

A mental model that sticks

Think of a coat check. Each coat gets a small numbered ticket, and instead of describing the coat every time, staff just compare tickets, which is instant. Occasionally two coats might share a ticket number because the ticket numbers are short, so before handing a coat back, the attendant glances at it to make sure it really is yours. A rolling fingerprint is the ticket, the glance is the verification step, and the rolling update is a ticket machine that can print the next ticket from the previous one without looking at the coat again.

Practice problems with answers

Try each one on paper before you tap to check.

1. What is 2718 mod 13?

1. Since 13 × 209 = 2717, the remainder is 1.

2. Slide the window 2718 to 7182 using the rolling formula mod 13. What is the new hash?

6. The weight is 10³ mod 13 = 12, so (1 − 2 × 12) × 10 + 2 = −228, and −228 mod 13 = 6. Directly, 7182 mod 13 is also 6.

3. A haystack has 19 digits and the needle has 5. How many windows are there?

15, at shifts 0 to 14. The count is the haystack length minus the needle length, plus 1.

4. Why does Rabin-Karp verify the letters after a fingerprint match?

Different strings can share a fingerprint. In my walk-through, the window 67399 had the same hash, 7, as the needle 31415 but was not a match.

5. Roughly how many false alarms should you expect with a modulus of 1,000 over 100,000 windows?

About 100, since each wrong window collides with probability near one in the modulus.

6. Two documents share 30 of the first document’s 120 fingerprints. How similar is the first to the second?

25 percent of the first document’s fingerprints appear in the second.

7. Why is a set of fingerprints useful when you have thousands of needles?

A set lookup takes about the same time however many needles it holds, so one pass over the text answers all of them at once.

Test yourself: five quick questions

Tap a question to reveal the answer. The correct option is marked.

What does the rolling hash let Rabin-Karp avoid?

1. Verifying matches
2. Recomputing each window’s fingerprint from scratch
3. Choosing a modulus
4. Reading the text at all

Each new fingerprint is derived from the previous one in constant time, so the window length does not matter.

Two different strings have the same fingerprint. What is this called?

1. A rolling hash
2. A border
3. A verification
4. A collision, or spurious hit

A collision. It is why a fingerprint match is only a candidate until the letters are compared.

What was the main effect of using a larger modulus in my test?

1. Far fewer false alarms
2. Faster letter comparison
3. More matches found
4. A longer needle

With a modulus near a billion there were no false alarms, against 2,041 for a modulus of 101.

When does Rabin-Karp really shine?

1. One short needle in a short text
2. Sorting a list
3. Searching for many needles in one pass
4. Finding the longest word

Fingerprints of all needles go into a set, and one pass over the text checks every window against it.

What is the worst-case time of Rabin-Karp?

1. n + m always
2. n × m, if nearly every window collides
3. m squared
4. Constant

If most windows collide, you verify almost every position, which is as slow as the naive method.

Frequently asked questions

What is the Rabin-Karp algorithm?

A string matching algorithm that compares numeric fingerprints of text windows with the fingerprint of the pattern, using a rolling hash to update each fingerprint in constant time, and verifies the real letters only when fingerprints match.

What is a rolling hash?

A hash function that can be updated cheaply when a window slides by one position. You remove the contribution of the letter that leaves and add the one that arrives, instead of rehashing the whole window.

What is the time complexity of Rabin-Karp?

Expected time is about O(n + m) with a good modulus. The worst case is O(n × m) when many windows collide, which is unlikely with a large, randomly chosen modulus.

Is Rabin-Karp better than KMP?

Not for a single needle. KMP guarantees linear time and avoids hashing. Rabin-Karp is better when you search for many needles at once or fingerprint documents.

Why use a prime number as the modulus?

Primes tend to spread remainders more evenly, reducing patterned collisions. Choosing the base or modulus at random also protects against inputs crafted to collide.

Can the fingerprint ever give a wrong final answer?

Not if you verify. A fingerprint match is only a candidate, and comparing the actual letters removes any false positive. Fingerprints never miss a true match, because equal strings always have equal fingerprints.