Worked examples — Rabin-Karp — rolling hash, O(n+m) expected

This is a hands-on companion to the Rabin-Karp topic note — see the parent, Rabin-Karp — rolling hash, where we derived the rolling hash. Here we drill it until no case can surprise you. Before we start, one reminder of every symbol we will use — nothing new, but let us re-anchor it so line one is readable.

Everything below rides on the two boxed facts from the parent:

---

The scenario matrix

Every problem Rabin-Karp can throw at you falls into one of these cells. The worked examples below are labelled with the cell(s) they cover, and together they hit all of them.

#	Case class	What is special about it	Covered by
C1	Ordinary match	pattern occurs once, hashes agree, verify passes	Ex 1
C2	No match anywhere	every window hash differs from $h(P)$	Ex 2
C3	Multiple / overlapping matches	pattern occurs more than once, windows overlap	Ex 3
C4	False positive (collision)	hashes agree but strings differ → verify must reject	Ex 4
C5	Degenerate sizes	$m=0$ (empty), $m=1$, $m=n$, or $m>n$ (empty answer)	Ex 5
C6	Negative-value trap	subtraction goes below zero under mod	Ex 6
C7	Adversarial worst case	crafted input where every window collides → $O(nm)$	Ex 7
C8	Real-world word problem	plagiarism / DNA style, choosing $b,q$	Ex 8
C9	Exam twist	"why is $q$ prime?" / off-by-one in $P_{\text{high}}$	Ex 9

---

Example 1 — Ordinary single match (cell C1)

Forecast: where do you expect the match — and at which index does the window "cd" begin? Jot it before reading.

Figure (s01) — what it shows: the text a c d drawn as three indexed boxes; a blue box outlines window 0 = "ac" (hash 2) and a pink box outlines window 1 = "cd" (hash 55), with a pink arrow showing the slide from window 0 to window 1 and the note that window 1's hash equals $h(P)$.

1. Compute $h(P)$. Read "cd" as a base-26 number: $2\cdot 26+3=55$. Why this step? The pattern's fingerprint is fixed; compute it once and compare against every window.
2. Compute window 0 = "ac". $0\cdot 26+2=2$. Why? This is our starting window; we must build its hash from scratch (Horner), $O(m)$.
3. Compare. $2\ne 55$ → skip instantly, no character comparison. Why? Unequal hashes prove the strings differ — that is the whole speed win.
4. Roll to window 1 = "cd". Here $P_{\text{high}}=b^{m-1}=26^1=26$. $H_1=((H_0-T[0]\cdot 26)\cdot 26+T[2])\mathrm{mod}101=((2-0)\cdot 26+3)\mathrm{mod}101=55.$ Why? Drop the leading 'a' (code 0), slide $\times 26$, add trailing 'd' (code 3) — all $O(1)$.
5. Compare & verify. $55=55$ → hashes agree → compare "cd" vs "cd" char-by-char → match at index 1. Why verify? Hash equality is necessary but not sufficient (see Ex 4).

---

Example 2 — No match anywhere (cell C2)

Forecast: how many character-by-character verifications should happen? (Hint: think about whether any window's hash can equal $h(P)$.)

1. $h(P)=1\cdot 26+0=26$. Why this step? 'b'=1, 'a'=0; we compute the pattern's fixed fingerprint once to compare against.
2. Window 0 = "aa": $0\cdot 26+0=0$. $0\ne 26$ → skip. Why? We must build the first window's hash from scratch; unequal to $h(P)$ means we skip in $O(1)$ with no char check.
3. Roll to window 1 = "aa": $H_1=((0-0\cdot 26)\cdot 26+0)\mathrm{mod}101=0$. $0\ne 26$ → skip. Why? All characters identical, so every window hash is $0$ — the roll confirms it stays $0$, still $\ne h(P)$.
4. No window ever equals $26$ → zero matches, zero verifications. Why this matters? It shows the best case: the hash filter rejects everything in $O(1)$ each, never touching a single character comparison.

---

Example 3 — Multiple overlapping matches (cell C3)

Forecast: windows overlap here — will Rabin-Karp find index 1 even though it overlaps index 0? Predict the full list of indices.

Figure (s02) — what it shows: the text a a a a as four indexed boxes; three coloured outlines (blue, pink, yellow) mark the three overlapping length-2 windows, each labelled "hash = 0 → match" at start indices 0, 1 and 2, making visible that overlapping windows are each checked separately.

1. $h(P)=0\cdot 26+0=0$. Why this step? Both pattern chars are 'a'=0, so the pattern fingerprint we compare against is $0$.
2. Window 0 = "aa": $0$. Match → verify → ✓ index 0. Why? Built from scratch; hash equals $h(P)$, so we must verify the actual chars — they agree, so index 0 is a real match.
3. Roll to window 1 = "aa": $H_1=((0-0)\cdot 26+0)=0$. Match → ✓ index 1. Why? Rolling (Drop-Slide-Add) keeps the hash at $0$; equal hash forces a verify, which passes even though this window overlaps index 0.
4. Roll to window 2 = "aa": $H_2=0$. Match → ✓ index 2. Why this matters? Rabin-Karp checks every start index independently, so overlaps are found naturally — no skipping like the failure-function idea in Knuth-Morris-Pratt.

---

Example 4 — False positive: a real collision (cell C4)

Forecast: $99$ and $200$ are different bytes. Can two different single characters share the same hash mod $101$? Guess yes/no.

1. Hash of code $99$: $99\mathrm{mod}101=99$. Why this step? A length-1 window's hash is just its code mod $q$; compute both to see if they clash.
2. Hash of code $200$: $200\mathrm{mod}101=200-101=99$. Why? Because $200-99=101=q$, the two differ by exactly one multiple of $q$, so they land on the same remainder. This is a collision.
3. If a text had byte $200$ where the pattern has 'c', their hashes match ⇒ Rabin-Karp is forced to verify char-by-char. Why? Equal hashes cannot be trusted; the algorithm must fall back to the actual bytes.
4. Verification compares actual bytes $99\ne 200$ → correctly rejects. Why this matters? The hash is a filter, not a proof. Skipping verification would report a phantom match. The rate of such events is roughly $1/q$ — see Birthday Paradox for the intuition on why collisions creep in faster than you'd think.

---

Example 5 — Degenerate sizes, including the empty pattern (cell C5)

Forecast: In case (a) an empty pattern — where does "nothing" occur inside "dog"? In case (d) how many windows even exist? Guess before reading.

1. (a) $m=0$ (empty pattern). By the standard convention an empty string occurs at every position $0,1,\dots ,n$, i.e. $n+1=4$ matches. There are no characters to hash, so Rabin-Karp guards this case first and returns $\{0,1,2,3\}$ without touching the hash machinery. Why guard? The formulas assume $m\ge 1$ (there is a "leading digit" to drop). With $m=0$ there is no window to build; we must special-case it or the loop over $b^{m-1}$ and window slices is meaningless.
2. (b) $m=1$. Then $P_{\text{high}}=b^{m-1}=b^0=1$. Each window is one char. $h(P)=14$. Windows: 'd'=3, 'o'=14, 'g'=6. Only window index 1 equals $14$ → match at 1. Why $b^0=1$? With one character there is nothing to shift; the leading weight is $1$.
3. (c) $m=n=3$. Exactly $n-m+1=1$ window (the whole text). $P_{\text{high}}=26^2=676\mathrm{mod}101$. $676=6\cdot 101+70$, so $P_{\text{high}}=70$. $h(\text{"dog"})=((3\cdot 26+14)\cdot 26+6)\mathrm{mod}101$. Inner: $3\cdot 26+14=92$. Then $92\cdot 26+6=2398$. $2398\mathrm{mod}101$: $101\cdot 23=2323$, $2398-2323=75$. So both $h(P)$ and the single window hash equal $75$ → match at 0. Why? Pattern equals the whole text, so exactly one window, and it matches.
4. (d) $m>n$. Number of windows $=n-m+1=3-5+1=-1<1$. There are no windows → return "no matches" immediately, before hashing. Why guard this? Building $P_{\text{high}}=b^{m-1}$ or a window hash when no window fits is meaningless and can crash indexing.

---

Example 6 — The negative-value trap (cell C6)

Forecast: After we drop the big leading 'z', the intermediate value might dip below zero mod $q$. Predict the sign before fixing.

Figure (s03) — what it shows: a chalk number line from below zero up past $q$; a pink arrow starts at the small reduced hash $44$, jumps left to $-606$ after subtracting the heavy leading-digit term $650$, then a yellow arrow "adds $q$" repeatedly (a blue bracket spanning multiples of $101$) to land back inside the legal band $[0,q)$ at $0$.

1. $h(\text{"za"})=25\cdot 26+0=650$. $650\mathrm{mod}101$: $101\cdot 6=606$, $650-606=44$. So $H_0=44$.
2. $P_{\text{high}}=26^1\mathrm{mod}101=26$.
3. Roll naively: $H_0-T[0]\cdot P_{\text{high}}=44-25\cdot 26=44-650=-606$. Why negative? The dropped digit's weight ($650$) is far bigger than the small reduced hash ($44$). Under mod arithmetic this is legal but a computer's % on a negative can misbehave.
4. Fix — add $q$ until non-negative, then continue. In code: ((44 - 650) % q + q) % q. $-606\mathrm{mod}101$: since $606=6\cdot 101$, we have $-606\equiv 0(\mathrm{mod}101)$. Reduced value $=0$.
5. Finish the roll: $H_1=(0\cdot 26+T[2])\mathrm{mod}101=(0+1)\mathrm{mod}101=1$.
6. Cross-check from scratch: $h(\text{"ab"})=0\cdot 26+1=1$. ✓ The fix gave the right answer.

---

Example 7 — Adversarial worst case (cell C7)

Forecast: with $q=3$, how many distinct hash values can exist? Predict how often the verify step runs on this text.

Figure (s04) — what it shows: six indexed boxes all 'a'; five overlapping length-2 window brackets, every one labelled "hash = 2 = h(P) → VERIFY", with a yellow banner "only 3 buckets {0,1,2}" to show why so many windows are forced to collide.

1. With $q=3$ every hash lives in $\{0,1,2\}$ — only 3 possible fingerprints. Why this hurts? With so few buckets, many windows are forced to share a hash (pigeonhole). See Birthday Paradox.
2. $h(P)=h(\text{"aa"})=(1\cdot 10+1)\mathrm{mod}3=11\mathrm{mod}3=2$. Why this step? Fix the pattern fingerprint we compare against.
3. Every window of $T$ is "aa" (all characters are 'a'), so every window hash is also $2$. Concretely window 0 = "aa" hashes $2$; rolling with $P_{\text{high}}=10^1\mathrm{mod}3=1$ gives $H_1=((2-1\cdot 1)\cdot 10+1)\mathrm{mod}3=(10+1)\mathrm{mod}3=2$, and likewise for every later window. Why? Because $T$ is a constant string, the hash never changes; here it also equals $h(P)$, so every window is a hash hit.
4. Every one of the $n-m+1=5$ windows is a hit → we run the $O(m)$ char verify 5 times. Why $O(nm)$? If (nearly) all $n-m+1$ windows hit, total cost $\approx (n-m+1)\cdot m=O(nm)$ — the naive cost, hashing wasted.
5. Fix: pick a large prime like $q=10^9+7$ (or double-hash) so collision chance $\approx 1/q$ is negligible. Why? A big modulus spreads hashes over billions of buckets, so distinct strings almost never share one and verification is rare — see Hashing for base/prime choice.

---

Example 8 — Real-world word problem: plagiarism check (cell C8)

Forecast: Two documents, hashing 5-grams — will the first window of $T$ match $P$? Guess before computing.

1. $h(P)=h(\text{"00101"})$, base 2 (Horner): $0;0\cdot 2+0=0;0\cdot 2+1=1;1\cdot 2+0=2;2\cdot 2+1=5$. So $h(P)=5\mathrm{mod}13=5$. Why base 2? Alphabet has 2 symbols; base = alphabet size keeps digits distinct.
2. First window of $T=\text{"10101"}$: bits $1,0,1,0,1$. Horner: $1;1\cdot 2+0=2;2\cdot 2+1=5;5\cdot 2+0=10;10\cdot 2+1=21;21\mathrm{mod}13=8$. So $H_0=8$. Why? Build the starting window from scratch; $8\ne 5$ → not a plagiarism hit at index 0.
3. Roll over $T^{\prime }=\text{"101010"}$ to window 1 = "01010" (bits $0,1,0,1,0$). Here $P_{\text{high}}=b^{m-1}=2^4=16\mathrm{mod}13=3$. $H_1=((H_0-T[0]\cdot 3)\cdot 2+T[5])\mathrm{mod}13=((8-1\cdot 3)\cdot 2+0)\mathrm{mod}13=(5\cdot 2+0)\mathrm{mod}13=10$. Why? Drop the leading '1' (weight 3), slide $\times 2$, add trailing '0' — the $O(1)$ shingle update.
4. Cross-check from scratch: $h(\text{"01010"})$ bits $0,1,0,1,0$: $0;1;2;5;10\Rightarrow 10\mathrm{mod}13=10$. ✓ Roll agrees. Why this matters? Real plagiarism detectors hash millions of shingles; the $O(1)$ roll is what makes it feasible — same idea as String Hashing for Substring Comparison.

---

Example 9 — Exam twist: off-by-one in $P_{\text{high}}$ (cell C9)

Forecast: the leading character of a length-$m$ window carries weight $b^{?}$. Predict the exponent before reading, then see when the wrong exponent stays hidden.

1. Correct weight is $b^{m-1}$. In $H_i=T[i]b^{m-1}+T[i+1]b^{m-2}+\cdots +T[i+m-1]b^0$, the $m$ characters carry exponents $m-1$ down to $0$; the leading one is $b^{m-1}$. For $m=2$: $b^1=26$. Why $m-1$ not $m$? There are $m$ digit slots for exponents $0,1,\dots ,m-1$; the highest available is $m-1$. Using $b^m$ invents a slot that does not exist.
2. Correct roll (recap of Ex 1). $H_1=((2-0\cdot 26)\cdot 26+3)\mathrm{mod}101=55=h(\text{"cd"})$. ✓ Why? This is the reference answer we compare the bug against.
3. Buggy roll on "acd". With $P_{\text{high}}=b^m=26^2=676\mathrm{mod}101=70$: $H_1^{\text{bug}}=((2-T[0]\cdot 70)\cdot 26+3)\mathrm{mod}101=((2-0\cdot 70)\cdot 26+3)\mathrm{mod}101=55.$ Why does the bug hide here? The dropped character is 'a'$=0$, so $T[0]\cdot P_{\text{high}}=0$ regardless of the weight — the wrong $P_{\text{high}}$ is multiplied by zero and vanishes. Graders love inputs like this because the bug is invisible.
4. Expose the bug — dropped char non-zero. Reuse the "za"→"ab" roll from Ex 6, where $T[0]=\text{z}=25$. Correct drop term: $25\cdot 26=650\equiv 44(\mathrm{mod}101)$. Buggy drop term: $25\cdot 70=1750$; $1750-17\cdot 101=1750-1717=33$, so $\equiv 33$. Why this proves it? $44\ne 33$: the subtraction is different, so $H_1$ comes out wrong — real matches get missed or phantom hits appear. The bug only ever hides when the dropped char is $0$.
5. Why must $q$ be prime? A prime $q$ makes the multiplicative structure of $\mathrm{mod}q$ well-behaved (no small factors that many strings share), so hashes spread evenly and collisions stay near $1/q$. A composite $q$ can let whole families of strings collapse to the same residue. See Modular Arithmetic. Why the exam asks this? It checks you understand $q$ controls collision spread, not just "keeps numbers small".

---

Wrap-up: which cell did each hit?

Connections

• Parent topic — the derivation
• Hinglish version
• Hashing — why large primes; base choice
• Modular Arithmetic — the +q fix, remainders
• Birthday Paradox — why collisions arrive sooner than expected
• String Hashing for Substring Comparison — same roll for $O(1)$ range equality
• Knuth-Morris-Pratt · Z-Algorithm — collision-free linear alternatives