A match decided by a number

The three algorithms before this one all compare characters. Rabin–Karp does something else: it summarises each window of the text as a number, compares that number against the pattern’s number, and only looks at characters when the two agree.

The summary is a hash, and hashing a window would be pointless if it cost a pass over the window — that would be the naive scan with extra arithmetic. What makes the algorithm work is that the hash rolls: the value for the window starting at $i+1$ is computed from the value at $i$ in constant time, by subtracting the character leaving and adding the character arriving.

So the whole text is summarised in one pass of arithmetic, and the character comparisons happen only where two summaries collide.

The roll, and the sign nobody expects #

The update itself is three operations and one of them is a trap.

Leaving the window is the character at position $i$, whose contribution to the hash is $c_i \cdot b^{m-1}$. Arriving is the character at $i + m$, whose contribution is $c_{i+m}$. So

$$h' = \big((h - c_i \cdot b^{m-1}) \cdot b + c_{i+m}\big) \bmod q$$

with $b^{m-1} \bmod q$ precomputed once. Constant time, no dependence on $m$, and the reason the whole algorithm is one pass.

The trap is that $h - c_i \cdot b^{m-1}$ can be negative, and the remainder operator in most languages — including the one this site’s libraries are written in — returns a negative remainder for a negative left operand. A hash of $-37$ then never equals the pattern’s hash of $972$, so the algorithm silently finds nothing at some positions and everything continues to look correct: no crash, no assertion, a plausible number of occurrences, and a few of them missing.

The string counter writes the correction out as ((th % mod) + mod) % mod rather than relying on the values staying positive, and the gate’s assertEveryMatcherAgrees is what would catch it — four algorithms are run on the same input and required to return identical occurrence lists, because a matcher that quietly misses an occurrence looks better on every counter. That is the direction that makes agreement worth checking rather than assuming.

Two counters, because there are two costs #

The string counter records Rabin–Karp with hashes and verifications kept apart, and the separation is the whole of the analysis rather than a convenience.

Hashes are the rolling updates: one per window, unavoidable, $n - m + 1$ of them and never more or fewer. On a 65,536-character text with a sixteen-character pattern that is 65,521, at every modulus, on every input. It is a constant of the algorithm.

Verifications are the character-by-character checks a collision forces. This is the variable, it is where every interesting property of the algorithm lives, and it is what the closed form predicts.

Reporting one number for both would hide exactly the term that varies, which is the same reason KMP’s preprocessing is counted separately from its search and the reason a Bloom filter’s probes are counted separately from its false positives.

The closed form, and a check on it #

If the hash spreads windows uniformly over $q$ residues, a window that is not an occurrence collides with probability $1/q$, and the expected number of spurious verifications is $(n - m + 1)/q$.

That is a prediction with a closed form, which on this site means it gets checked against a run rather than quoted. Across the sweep, at $n = 65{,}536$ and $m = 16$:

• $q = 101$: predicted 648.7, measured 675
• $q = 509$: predicted 128.7, measured 137
• $q = 1{,}009$: predicted 64.9, measured 79
• $q = 4{,}093$: predicted 16.0, measured 22

The agreement is good and it is not perfect, and the direction of the discrepancy is consistent — measured is always a little above predicted. That is the same finite-size effect the probe formula nobody checks documents for open addressing: the text’s windows are not independent draws, because consecutive windows share $m - 1$ characters, so the collisions are slightly correlated and slightly more numerous than a model of independent draws expects.

At the large end the counts become too small to say anything — one or two verifications, where the prediction is 4.0 or 1.0 — and the honest response is to stop asserting agreement there rather than to claim it. The generator does two things about it. It checks the closed form only where the prediction exceeds four, and the tolerance it checks against shrinks as the prediction grows: $0.25 + 3/\sqrt{\text{expected}}$, which is three standard deviations of Poisson noise plus a quarter for the window correlation above. A flat tolerance passed the long text and failed a shorter one whose numbers were perfectly ordinary, which is the measurement being right and the check being wrong.

What a verification actually costs #

The number of verifications is not the cost. What matters is the number multiplied by how long each one runs.

At $q = 101$ there were 675 verifications and 731 character comparisons in total. That is 1.08 characters per verification. A colliding window on random text is a window whose characters are unrelated to the pattern’s, so the check fails on the first character essentially always, and 675 collisions cost 731 characters rather than $675 \times 16 = 10{,}800$.

A collision is cheap when the colliding string is unrelated to the pattern. That sentence contains the whole of the attack in the second half of this essay, because an adversary’s job is to make it false.

That figure needs its qualification stated plainly. Rabin–Karp’s character count is near zero, and it is not a sublinear algorithm in any sense: it touches every character of the text twice, once entering the window and once leaving it. The counter that would rank it fairly against Horspool is a counter of arithmetic operations, and this site does not have one.

What the character counter is good for here is the thing it was built for — showing that verification cost is a separate resource that can be driven up independently of everything else.

The modulus is not a free choice #

At $q = 257$ the measured verifications are 693 against a predicted 254.9 — a factor of 2.7, at a modulus that is prime, is comfortably larger than the alphabet, and would pass any casual inspection.

The reason is arithmetic and it is not subtle once seen. The base is 256 and $256 \equiv -1 \pmod{257}$. So the hash

$$h = c_0 b^{m-1} + c_1 b^{m-2} + \cdots + c_{m-1} \pmod q$$

collapses to an alternating sum of the window’s characters: $c_0 - c_1 + c_2 - \cdots$. For a sixteen-character window of letters that quantity ranges over a few hundred values rather than over 257 residues uniformly, and — worse — it is unchanged by swapping any two characters two positions apart.

A modulus chosen for being prime, with no reference to the base, gets this. The rule that follows is not “use a big modulus”; it is that $q$ must not be close to a power of the base, and the failure is silent: every count is still correct, every occurrence is still found, and the algorithm is a constant factor slower in a way no test would report.

This is the third time on this site that a hash has failed because of a relationship between two constants nobody wrote down together — the probe formula and a hash is a family, not a function are the other two — and the pattern is the same each time. The analysis assumes uniformity; the implementation has structure; nothing checks.

Building the collisions on purpose #

The closed form assumes the text was not chosen with the hash in mind. The adversary who knows the seed makes the general argument: a randomised algorithm whose randomness is public is not randomised, and a hash whose parameters are in the source is public.

The construction here is elementary. To make a verification expensive it is not enough that a block collides — a colliding block that differs from the pattern immediately costs one character comparison. What is needed is a block that collides and agrees with the pattern for a long way, so that the check runs almost to the end before failing.

Take the pattern’s first $m-2$ characters and search over the last two. Two such blocks have hashes differing by $d_1 \cdot 256 + d_2$ where each $d$ is a character difference, so the difference is at most 65,535 in absolute value. Whether a collision exists at all is therefore decided by one comparison:

At $q = 1{,}009$ the construction finds 8 distinct colliding blocks, against an expectation of $94^2/1009 = 8.76$ from enumerating printable pairs — agreement close enough to say the search space is being explored as modelled.

At $q = 1{,}000{,}003$ it finds none, and cannot. The hash difference cannot reach a modulus larger than 65,536, so no two-character variation of the pattern collides with it. The attack is not merely hard there; it is arithmetically impossible for this construction.

That is a considerably sharper statement than the usual advice, and it is checkable rather than reassuring. The gate asserts both halves — that the collisions exist at the small modulus and that they do not exist at the large one — because a construction that quietly succeeded everywhere would be measuring something other than what it claims.

Two more sweeps say what the defect is a property of, and neither of them is the text. Double the pattern and the collision rate at a good modulus halves, exactly as $n/q$ says it should; the degenerate modulus stays degenerate and its overshoot falls with it, because the alternating sum has fewer terms to cancel.

And narrowing the alphabet does not rescue it either, which is the case a reader might expect to be safe because a small alphabet makes every window’s hash more likely to collide anyway.

Nor is it a property of the six moduli that happen to be on the plate. Six different primes, the same base, and the same one modulus is off the line — because the one that is off is not one of the six.

What the attack costs the algorithm #

Cycling those 8 blocks into a text of 1,024 characters and searching it for the pattern:

• 1,009 windows examined
• 64 verifications, one at each aligned block
• 960 character comparisons, exactly 15 per verification
• 0 occurrences found

Fifteen of the pattern’s sixteen characters, every time, on a text where the pattern does not appear. Against the random-text baseline at the same modulus, the same length of text would expect one verification costing about one character. The attack has multiplied the verification cost by roughly a thousand while leaving the hash count, the answer, and every other measurable property untouched.

Scaled up, this is $\Theta(nm)$: the algorithm’s worst case, reached on an input a page of arithmetic produces, at a modulus that looks fine.

An accident that behaves like an attack #

One further measurement, found while writing the check rather than while writing the essay.

The first version of the adversary used abababababababab as the pattern, and its verification cost came out at 8.01 characters rather than the expected 15 — and 505 of 1,009 windows verified rather than 64.

The pattern is periodic, and a periodic pattern collides with itself under a shift. Shifting abababababababab by two characters gives back the same string, so a window offset by two from a colliding block collides too, and its verification fails after 13 characters instead of 15; offset four fails after 11, and so on down. Half the windows verify, at costs from 15 down to 1, and the mean is 8.

Nothing was wrong with the construction. The victim was wrong, and the assertion that caught it was the one demanding the cost per verification be near $m$. That is the third time in this site’s history that an assertion has rejected the code building the case rather than the code being measured, and it is why the check reads the way it does now, with the choice of a non-periodic pattern justified in a comment above it.

It is also a real property worth keeping: a periodic pattern is its own partial adversary, and it needs no attacker.

The counter that does not exist, estimated anyway #

The qualification above says the character counter cannot rank this algorithm fairly and that no counter of arithmetic operations exists here. That is true, and the estimate is worth making anyway, because the gap turns out to be large enough that no plausible accounting closes it — and because the direction is the opposite of what the plate shows.

Count a memory read and an arithmetic operation as one unit each, on the 20,000-character text with $m = 8$ drawn above.

Rabin–Karp performs 19,993 rolling updates. Each is a subtract, a multiply, an add and a remainder, plus the add and second remainder the sign correction requires — six, and the hash comparison at each window makes seven. That is about 140,000 units, and essentially none of them are the character comparisons the counter draws.

Horspool examines about a seventh of the characters at this pattern length, so roughly 2,857 alignments. Each is a shift-table lookup and a comparison, with the shift arithmetic on top — call it three. About 8,600 units.

So the honest ranking on ordinary text is Horspool ahead by something between ten and twenty times, on the algorithm the character plate shows as spending almost nothing. The plate is not merely incomplete about Rabin–Karp; read as a ranking it is inverted, which is a stronger criticism of it and the reason the qualification is repeated wherever the plate appears.

Two things sharpen it further and neither needs a counter.

The remainder is not one unit. Integer division is the slowest arithmetic instruction on ordinary hardware by a wide margin, typically tens of times an add’s latency, and there are two per update. Any weighting that reflects that widens the gap rather than closing it, so the estimate above is generous to the algorithm it is against.

And the gap grows with the pattern. Rabin–Karp’s cost is flat in $m$ — that is what the sweep plate shows, and it is the algorithm’s genuine distinguishing property. Horspool’s falls with $m$, because a longer pattern shifts further. So the two never cross as the pattern lengthens; the algorithm that ignores $m$ loses to the one that exploits it, by more at every size.

Which locates the crossing where it actually is, and it is not on this axis at all. Searching for $k$ patterns costs Horspool $k$ passes — about 8,600 units each — while Rabin–Karp keeps its 140,000 and adds one set lookup per window. Setting those equal puts the crossing at about twenty patterns, and past it the single-pass structure wins by the full factor of $k$.

That is the quantitative form of the claim the shift the pattern already knows leaves implicit, and it is a much narrower recommendation than “use a rolling hash”. For one pattern on ordinary text, do not: an algorithm reading a seventh of the characters beats one doing arithmetic on all of them. For twenty or more, do, and the reason is the same one that makes a filter allowed to be wrong worth its false positives — a cheap test applied once to each position, with the expensive test reserved for what survives.

The estimate is an estimate and is labelled as one. What makes it worth writing down rather than deferring to a counter nobody has built is that its conclusion is a factor of ten with a stated model, and a measurement disagreeing with it by less than that would not change any of the advice above.

Where this leaves the four algorithms #

Rabin–Karp is the only one of the four whose cost is a distribution rather than a number, and that is its whole character. The other three are deterministic: given a text and a pattern, their counts are fixed, and the interesting question is which inputs are bad. Here the counts depend on a modulus chosen by the implementer, and the interesting question is what the implementer assumed about the text.

Expected is not average is the essay that draws the distinction this rests on, and it applies exactly. The $n/q$ formula is an expectation over an assumption about the input, not a guarantee over inputs — so it says nothing at all about a text somebody built, and it does not say what a real hash on real text will do either, only what an idealised one would.

What the algorithm is genuinely good at, and what nothing here has measured, is the case the other three cannot do: many patterns at once. Hash all $k$ patterns, put the values in a set, roll one hash along the text, and look each window up. The cost is one pass and $k$ lookups’ worth of memory, against $k$ passes for anything else.

That structure should look familiar. A cheap probabilistic filter in front of an expensive exact check, where the filter may say yes wrongly and never says no wrongly, is precisely a filter that is allowed to be wrong — and the two share more than a shape. Both have a false-positive rate with a closed form, both spend the saved work on verifying the positives, and both are undone by the same thing, which is somebody choosing the input with the hash in hand. The Bloom filter’s answer to that is a hash family chosen at run time; Rabin–Karp’s is a modulus chosen at run time, and almost no implementation does it.

The other setting where the rolling hash is the whole idea is one where there is no pattern at all. Content-defined chunking rolls a hash along a file and cuts a chunk boundary wherever the value has some number of low bits zero. Insert a byte at the front of the file and every boundary after the insertion is in the same place as before, because each is decided by the last few bytes rather than by an offset — which is what makes deduplicating storage and incremental sync work, and which a fixed-size chunker cannot do at all. Nothing is being matched; the only property being used is that the summary rolls.

That is the honest place for this algorithm in the collection. As a substring search it is beaten on ordinary text by an algorithm that reads a seventh of the characters, and it is the only one of the four whose worst case an outsider can arrange. As a way of summarising every window of a stream cheaply, it has no competition among the other three, because none of them produces a summary at all.