Fingerprinting and String Matching

The question

Here is a text of sixteen digits and a pattern of four. Where does the pattern occur?

The answer is at positions 3 and 12 (counting from 0). Now scale it up. Two data centres each hold a copy of a 1 GB file, and one copy may have been corrupted. Are they still equal? Or a text of a hundred thousand characters and a pattern of fifty: where does the pattern occur?

Both questions compare big objects, and the obvious way reads all of both. This module replaces each object by a fingerprint, its remainder modulo a prime chosen at random. Equal objects always have equal fingerprints. Different ones almost never do, and we can say exactly how rarely. Then we slide the fingerprint along a text in constant time per step, which is the Karp–Rabin algorithm.

The naive approach, and where it wastes work

To find a pattern of length $m$ in a text of length $n$, try each of the $n-m+1$ starting positions and compare characters until one differs. On most texts the first comparison fails and this is fast. On the worst texts it isn't:

def naive_comparisons(text, pat):
    """Character comparisons made by the obvious scan, and the positions it finds."""
    count, found, m = 0, [], len(pat)
    for i in range(len(text) - m + 1):
        for j in range(m):
            count += 1
            if text[i + j] != pat[j]:
                break
        else:
            found.append(i)
    return count, found

TEXT, PAT = "6328465307928465", "8465"
assert naive_comparisons(TEXT, PAT)[1] == [3, 12]

n = 10_000
assert naive_comparisons("a" * n, "a" * 49 + "b")[0] == 50 * (n - 49)

On the text aaa…a with the pattern a…ab (49 a's, then b), every position matches 49 characters before failing on the 50th: $50(n-49)$ comparisons, $\Theta (nm)$. The waste is exact. Moving one step right, the scan throws away 49 characters it has just read and reads 48 of them again.

For the two files it is worse: comparing them means sending one of them across, $8·{10}^9$ bits.

The model: coins after the input

We count word operations: arithmetic on numbers that fit in a machine word (below $T·B$ here, for the prime range $T$ and the base $B$ defined below) costs one step, and so does reading or comparing one character.

The algorithms here flip coins, and the guarantee is about those coins. The input is fixed first, by anyone, even an adversary. Then the algorithm picks its prime. Every probability below is over that choice, for every input. This is the same setting as universal hashing in module 04: nothing is assumed about the data.

Comparing remainders

Alice holds an $n$-bit number $x$ (her file, read as one big binary number), and Bob holds $y$. Alice picks a random prime $p\le T$ and sends the pair $(p,xmodp)$. Bob answers "equal" if $ymodp$ is the same number.

If $x=y$, Bob is always right. If $x\ne y$, Bob is wrong exactly when $x\equiv y\left(\mathrm{mod}p\right)$, that is, when $p$ divides $D=|x-y|$. So the question becomes: how many primes can divide one fixed nonzero number?

Lemma. A number $1\le D<2^n$ has fewer than $n$ distinct prime factors. Proof: if $q_1,\dots ,q_k$ are distinct primes dividing $D$, their product divides $D$, and each is at least 2, so $2^k\le q_1\cdots q_k\le D<2^n$, and $k<n$.

The first equality is exact, and on small numbers you can count it:

import math

def primes_upto(T):
    sieve = bytearray([1]) * (T + 1)
    sieve[0] = sieve[1] = 0
    for q in range(2, math.isqrt(T) + 1):
        if sieve[q]:
            sieve[q * q::q] = bytearray(len(sieve[q * q::q]))
    return [q for q in range(T + 1) if sieve[q]]

x, y = 9_876_543, 9_366_033
assert x - y == 510_510 == 2 * 3 * 5 * 7 * 11 * 13 * 17
assert x < 2**24 and y < 2**24
fooled_100 = [q for q in primes_upto(100) if x % q == y % q]
assert fooled_100 == [2, 3, 5, 7, 11, 13, 17] and len(primes_upto(100)) == 25
fooled_1000 = [q for q in primes_upto(1000) if x % q == y % q]
assert len(fooled_1000) == 7 and len(primes_upto(1000)) == 168

These two 24-bit numbers differ by $510510$, the product of the first seven primes, which is about as unlucky as a difference can be. With $T=100$, 7 of the 25 primes fool Bob (error $0.28$). With $T=1000$ there are still only those 7 bad primes, but now among 168 (about $0.042$). The bad primes are fixed by the input; raising $T$ adds only good ones.

How many primes are there?

The bound $n/\pi (T)$ is only useful if we know $\pi (T)$, the number of primes up to $T$. The prime number theorem (stated, not proved here) says $\pi (T)~T/\ln T$: about one number in $\ln T$ is prime. For a proof we need an inequality that holds at every $T$, not just in the limit. Rosser and Schoenfeld proved one (stated here):

$$\pi (T)>\frac{T}{\ln T}\text{for every }T\ge 17.$$

flags = bytearray(20_001)
for q in primes_upto(20_000):
    flags[q] = 1
count = 0
for T in range(2, 20_001):
    count += flags[T]                         # count == pi(T)
    assert T < 17 or count > T / math.log(T)

table = {T: (len(primes_upto(T)), T / math.log(T)) for T in (100, 1000, 10**4, 10**6)}
assert table[100][0] == 25 and table[1000][0] == 168
assert table[10**4][0] == 1229 and table[10**6][0] == 78498
assert round(table[10**6][1]) == 72382

Primes are plentiful, and that has a second use: a random prime is cheap to draw. Pick a uniform integer in $[2,T]$ and keep it if it is prime. Each draw succeeds with probability $\pi (T)/(T-1)$, so the expected number of draws is $(T-1)/\pi (T)$, which is less than $\ln T$ by the inequality. For $T={10}^6$ that is $12.7$ draws. Rejection also keeps the prime uniform over the primes up to $T$, which is exactly what the theorem assumes.

Now choose $T$. With $T=n^2$ the inequality gives $\pi (n^2)>n^2/(2\ln n)$, so the error is below $n·2\ln n/n^2=2\ln n/n$. For the 1 GB files, $n=8·{10}^9$ bits:

nbits = 8 * 10**9
assert math.ceil(math.log2(nbits**2)) == 66          # p and x mod p fit in 66 bits each
error = 2 * math.log(nbits) / nbits
assert 5.6e-9 < error < 5.8e-9

Alice sends 132 bits instead of eight billion, and Bob is fooled with probability below $5.7·{10}^{-9}$, whatever the files are. If that is not small enough, repeat with fresh primes: $k$ independent rounds multiply the error to below $(5.7·{10}^{-9}{)}^k$.

Rolling the fingerprint along a text

Back to the digits. Read each window of $m=4$ digits as a number $W_i$ and the pattern as $P$. The pattern occurs at $i$ exactly when $W_i=P$, so we could compare $W_{i}modp$ with $Pmodp$. Computing each $W_{i}modp$ from scratch costs $m$ steps per window, which is no better than the naive scan. The point of Karp–Rabin is that the next window's value follows from the previous one. Drop the leading digit $t_i$, shift, and bring in $t_{i+m}$:

$$W_{i+1}=(W_i-t_i·B^{m-1})·B+t_{i+m},$$

in base $B=10$ for digits. Going from 6328 to 3284 is $(6328-6000)·10+4$. This is exact arithmetic, and reduction mod $p$ respects $+$, $-$ and $\times$, so the same identity holds for the remainders once $B^{m-1}modp$ is precomputed. That makes it two multiplications, an addition and a subtraction per step, whatever $m$ is. With $p=13$, ${10}^{3}mod13=12$:

p = 13
fp = [int(TEXT[i:i + 4]) % p for i in range(13)]          # from scratch, to check against
assert int(PAT) % p == 2 and pow(10, 3, p) == 12
assert fp == [10, 8, 12, 2, 12, 4, 3, 11, 12, 11, 2, 12, 2]
for i in range(12):                                       # the roll gives the same numbers
    assert ((fp[i] - int(TEXT[i]) * 12) * 10 + int(TEXT[i + 4])) % p == fp[i + 1]

The first step, by hand: $((10-6·12)·10+4)mod13=(-620+4)mod13=8$, and indeed $3284=252·13+8$.

The invariant holds at $i=0$ because the first window is computed directly, and each roll preserves it by the identity above. By induction it holds for every window.

The trace, and a false alarm

All thirteen residues are 10 8 12 2 12 4 3 11 12 11 2 12 2. Three windows share the pattern's residue 2: positions 3, 10 and 12.

assert TEXT[10:14] == "9284" and 9284 - 8465 == 819 == 3 * 3 * 7 * 13
assert [q for q in primes_upto(50) if 819 % q == 0] == [3, 7, 13]

How many false alarms?

A window $W_i\ne P$ is a false positive when $p$ divides $W_i-P$. Both are $m$-digit numbers in base $B$, so $0<|W_i-P|<B^m=2^{m{\log }_{2}B}$, and by the lemma this difference has fewer than $m{\log }_{2}B$ prime factors. So

$$Pr[\text{window }i\text{ is a false positive}]<\frac{m{\log }_{2}B}{\pi (T)}.$$

The false positives in a text are not independent of each other, since one prime decides all of them. That doesn't matter. Linearity of expectation needs no independence, so the expected number of false positives is the sum over windows:

$$E[\text{false positives}]<\frac{(n-m+1)m{\log }_{2}B}{\pi (T)}.$$

On our text we can compute the expectation exactly. Draw $p$ uniformly from the 15 primes up to 50 and count, for each of the 11 non-matching windows, how many of those primes divide its difference from 8465:

from fractions import Fraction

small = primes_upto(50)
bad = sum(sum(1 for q in small if (int(TEXT[i:i + 4]) - 8465) % q == 0)
          for i in range(13) if TEXT[i:i + 4] != PAT)
assert len(small) == 15 and bad == 14
assert Fraction(bad, 15) == Fraction(14, 15)
# a difference below 10**4 has at most 5 distinct prime factors: 2*3*5*7*11 = 2310 < 10**4 < 30030
assert math.prod(primes_upto(11)) == 2310 and math.prod(primes_upto(13)) == 30030

The exact expectation is $14/15\approx 0.93$ false positives. The bound, which charges every one of the 11 windows the most prime factors a difference below ${10}^4$ can have (five), gives $11·5/15\approx 3.67$. It is loose, but it holds for every text, and it is what tells us how to pick $T$: with $B=256$, $m=50$ and $n={10}^5$, $T={10}^9$ gives fewer than 0.83 expected false positives in the whole text.

bound = 10**5 * 50 * 8 / (10**9 / math.log(10**9))    # pi(10**9) > 10**9 / ln(10**9)
assert 0.82 < bound < 0.84
assert 50 * 8 == 400 and len(primes_upto(1000)) == 168     # T = 1000 is useless for m = 50, B = 256

Monte Carlo or Las Vegas

A candidate is not yet a match. There are two honest things to do with it.

• Monte Carlo: report every candidate. The time is always $O(n+m)$, and the answer is wrong with probability at most the bound above. On our text with $p=13$ it reports 3, 10 and 12.
• Las Vegas: compare each candidate with the pattern character by character, and report it only if they agree. The answer is never wrong, whatever the prime. What is random now is the time: each false positive costs up to $m$ extra comparisons. With $p=13$ it reports 3 and 12.

Checking turns a small probability of a wrong answer into a small expected cost. The error is one-sided in both versions: a true occurrence always has the pattern's residue, so neither version ever misses one.

Complexity

In the word model:

• Equality of two $n$-bit files: $2\lceil {\log }_{2}T\rceil$ bits sent, one-sided error below $n/\pi (T)$; with $T=n^2$, 132 bits and error below $5.7·{10}^{-9}$ for 1 GB.
• Karp–Rabin, Monte Carlo: $O(m)$ to fingerprint the pattern and the first window, $O(1)$ per roll, so $O(n+m)$ word operations on every input, with error probability below $nm{\log }_{2}B/\pi (T)$.
• Karp–Rabin, Las Vegas: always correct, in expected time $O(n+m+m·(\text{occ}+E[\text{false positives}]))$, where occ is the number of true occurrences. The expectation is over the prime, on every input.

The occurrences term is real. On the text aaa…a with the pattern aaaa every window is a true occurrence, and checking them all costs $\Theta (nm)$. The Knuth–Morris–Pratt algorithm finds all occurrences deterministically in $O(n+m)$ even then. No exact matcher can beat $\Omega (n)$, because a character it never reads could complete an occurrence. Where fingerprints win is in comparing many strings or substrings at once, where one pattern-specific table is not enough.

Measure the claim

On aaa…a with the pattern of 49 a's and a b, every window differs from the pattern by exactly 1 in the last digit, and 1 has no prime factors. So Karp–Rabin never raises a false alarm here, and its cost is one roll per window. The naive scan pays 50 per window:

for n in (10**3, 10**4, 10**5):
    windows = n - 49
    naive = 50 * windows                      # counted exactly above, at n = 10,000
    assert abs(ord("a") - ord("b")) == 1      # |W_i - P| = 1: no prime divides it
    print(n, round(naive / n, 2), round(windows / n, 3))
assert naive_comparisons("a" * 1000, "a" * 49 + "b")[0] == 50 * (1000 - 49)

The naive ratio climbs towards $m=50$ and Karp–Rabin's stays at 1, the $\Theta (nm)$ against $O(n)$ gap. On a random text, where the naive scan usually fails at the first character, both would be cheap. The worst case is where the proof earns its keep.

A problem that looks different

A backup service keeps yesterday's disk image. Today's image holds mostly the same data, but with bytes inserted and deleted at unknown places, so nothing lines up. Which 4 KB stretches of today's image already exist somewhere in yesterday's, at any byte offset? Sending them again wastes bandwidth. Nothing in the question mentions patterns or primes. The lab's last problem is a different one.

Practise

The lab starts with the rolling fingerprint, drawn one window at a time, with a check that it really rolls and doesn't recompute. It then traces the candidates on a new text and separates the true matches from a false alarm. After that you write a matcher that draws its own random prime and works with or without the check, measure what it reads per character against the naive scan, and count false alarms exactly. The last problem doesn't say what it is.

Recap

• You can now: bound the error of comparing remainders by (prime factors of the difference) / (primes up to $T$), and pick $T$ with the prime number theorem; roll a window's residue in constant time; trace Karp–Rabin by hand, false positive included; and turn a Monte Carlo matcher into a Las Vegas one by checking each candidate.
• Invariant: the rolling value is the current window's remainder, so a window is a candidate exactly when the random prime divides its difference from the pattern, and a fixed nonzero difference has fewer prime factors than it has bits.
• Complexity achieved: $O(n+m)$ word operations with error below $nm{\log }_{2}B/\pi (T)$, or never wrong in expected $O(n+m+m·\text{occ})$ for a large enough $T$, against $\Theta (nm)$ for the naive scan; file equality in $O(\log n)$ bits instead of $n$.
• Failure mode: a prime fixed before the input is known, or a $T$ too small for $nm{\log }_{2}B$, which makes the bound say nothing. With $B=256$ and $m=50$ a difference can have up to 399 prime factors, and there are only 168 primes below 1000.
• In real software: rsync finds blocks that two versions of a file share with a weak checksum that it rolls one byte at a time, and confirms each candidate with a strong hash before trusting it. That is the same filter-then-check pattern as Las Vegas Karp–Rabin.
• Next: module 06 answers range queries with a tree whose every node already knows the answer for its block.

Check yourself

1. Why does sending $(p,xmodp)$ with a random prime $p\le n^2$ detect $x\ne y$ with high probability, and why must the prime be chosen after the files are fixed?
2. Keep the prime fixed but choose the base $B$ at random instead. Is Karp–Rabin still safe against a text chosen by an adversary?
3. On the text aaa…a with the pattern aaaa, and on a random text over 26 letters, compare Las Vegas Karp–Rabin with the naive scan and with Knuth–Morris–Pratt. Which one wins where?

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.