Rabin-Karp is quoted as expected O(n+m) — what input forces O(n*m), and how do you defend against it?

## What "expected" is actually quantifying Expected O(n+m) is a statement about the *number of spurious confirmations*: it assumes that, across n offsets, only a constant number of fingerprint hits are collisions rather than matches. Where does the randomness come from? Not from the text — the text is whatever it is. It comes from the choice of hash parameters. When the base and modulus are drawn from a large family, the probability that any specific pair of unequal windows collides is small, so over the whole scan the expected spurious count is roughly n/M. That wording matters because expected is not worst case and not amortized. An expected bound averages over your own coin flips; it promises nothing about any single scan and, crucially, it collapses entirely if the parameters are fixed and known — then there are no coin flips left to average over, and an adversary can choose the input after seeing them. ## Route one to the worst case: adversarial collisions Suppose your service exposes a search where users supply the text (or the pattern) and your fingerprint uses a hard-coded base and modulus that anyone can read. Constructing windows that share the pattern's fingerprint is then straightforward algebra, not luck. An attacker submits a document where **every** offset is such a window. Each one triggers a confirmation, each confirmation reads up to m symbols and fails, and the scan does (n-m+1)*m work. For a 1 MB document and a 1 KB pattern that is a billion symbol comparisons per request — a single cheap request consuming enormous CPU, repeated at will. This is a request-amplification denial of service, and it is the reason "expected O(n+m)" should never be written on a design document as though it were a guarantee. ## Route two: honest, unavoidable matches The second route has no attacker. If the pattern occurs at a constant fraction of offsets — a repetitive fixed-width record format, a padded field, a low-complexity sequence — then confirmations fire because they should. Even a hypothetically collision-free fingerprint cannot help: the matches are real and each is confirmed at O(m). This case is *output-driven*, and recognising it is what separates a candidate who has thought about the algorithm from one reciting a bound. The fix is not a better hash; it is either accepting the cost, capping reported occurrences, or choosing a matcher that reports overlapping occurrences without re-reading each one. ## Defending the first route **Randomize the parameters per run and keep them internal.** Draw the base (and where practical the modulus) from a wide family at process start. An attacker who cannot observe them cannot precompute collisions, which restores the coin flips the expected bound needs. Do not derive them from anything guessable, and do not report them in errors or debug output. **Widen the range.** The accidental hit rate is about n/M; going from a narrow to a wide fixed-width modulus takes that from "visible in the profile" to "never happens". Width is the cheapest lever available and it costs nothing per operation. **Bound the damage.** Count confirmations per scan. If they exceed a small multiple of the expected count, you are either under attack or on pathological input; switch to a matcher with a worst-case linear guarantee, or reject the request. Cap the text and pattern sizes a single request may present. Put the scan on a timeout and a CPU budget like any other untrusted-input workload. **Measure it.** Confirmations-per-scan is a genuinely useful metric: it is near zero in health, and it is the first number to move under both attack and input drift. A p99 latency spike on a search path with a flat request rate and a climbing confirmation count is a diagnosis, not a mystery. ## The judgment to voice Rabin-Karp's expected bound is excellent and its worst case is bad, and which one you get is decided by who controls the input. On your own trusted corpus with sensible parameters, the expected bound is a fair description of production behaviour. On attacker-supplied input with fixed public parameters, the worst case is not a tail risk — it is a target. State that distinction explicitly; it is the answer the question is really asking for.