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

WHAT: we expand $H$ term by term. WHY: the leftmost character is the most significant digit, so it multiplies the highest power of $b$. $H(\text{cat})=2\cdot 26^2+0\cdot 26^1+19\cdot 26^0.$ Compute: $2\cdot 676=1352$, plus $0$, plus $19=1371$. The first character c carries $b^2=676$.

Conclude: the strings are definitely different. Equal strings always produce equal hashes, so unequal hashes force unequal strings. Do: skip this window instantly — no character check needed. (Contrast: a hash match only means "probably equal," so it needs verification.)

From L1.1 the raw value is $1371$. WHY mod: we keep it small and bounded. $1371=13\cdot 101+58$, since $13\cdot 101=1313$ and $1371-1313=58$. $H(\text{cat})\mathrm{mod}101=58.$

Precompute $P_{\text{high}}=b^{m-1}\mathrm{mod}q=26^2\mathrm{mod}101=676\mathrm{mod}101$. Since $676=6\cdot 101+70$, $P_{\text{high}}=70$. Drop leading c$=2$: $58-2\cdot 70=58-140=-82$. Keep non-negative: $(-82\mathrm{mod}101)=101-82=19$. Slide ($\times b$) and Add trailing s$=18$: $(19\cdot 26+18)\mathrm{mod}101=(494+18)\mathrm{mod}101=512\mathrm{mod}101$. $512=5\cdot 101+7$, so $H_1=7$. Check by direct formula: $H(\text{ats})=0\cdot 676+19\cdot 26+18=494+18=512$; $512\mathrm{mod}101=7$. ✓ The roll and the direct computation agree — that is the whole point.

$h(P)=0\cdot 26+1=1$. Window 0 "aa" $=0\cdot 26+0=0\ne 1$ → skip. Roll to window 1 "ab": $P_{\text{high}}=26^1\mathrm{mod}101=26$. $H_1=((0-0\cdot 26)\cdot 26+1)\mathrm{mod}101=1$. Matches $h(P)$ → verify → "ab"=="ab" ✓. Match at index 1.

$H(\text{ac})=(0\cdot 26+2)\mathrm{mod}3=2$. $H(\text{ba})=(1\cdot 26+0)\mathrm{mod}3=26\mathrm{mod}3=2$. They collide ($2=2$) even though the strings differ. Consequence: with a small $q$, many windows produce equal hashes, so we run the $O(m)$ verification constantly → the "expected $O(n+m)$" collapses toward the worst case $O(nm)$. This is exactly why we choose a large prime like $10^9+7$. See Modular Arithmetic and Birthday Paradox.

WHY this tool: expected count $=$ (number of trials) $\times$ (per-trial probability), the linearity-of-expectation shortcut. $\mathbb{E}[\text{spurious}]\approx N\cdot \frac{1}{q}=\frac{10^6}{10^9+7}\approx 10^{-3}.$ About one in a thousand whole searches does even a single wasted verification — negligible. That is why total expected cost stays $O(n+m)$.

Take $T=\text{"aaaa...a"}$ ($n$ copies) and $P=\text{"aaa...a"}$ ($m$ copies). Every window equals $P$, so every hash matches and every window triggers a full $O(m)$ verification. Total $=(n-m+1)\cdot O(m)=O(nm)$. Note this is a genuine-match worst case; an adversarial collision worst case instead uses a known small $q$ and crafts distinct windows that all hash to $h(P)$. Both defeat the average-case bound. This is why Knuth-Morris-Pratt (guaranteed $O(n+m)$) is preferred when adversaries are possible.

WHY independence multiplies: two independent events both happen with probability equal to the product. Combined rate $\approx \frac{1}{q_1}\cdot \frac{1}{q_2}=\frac{1}{101\cdot 103}=\frac{1}{10403}$. A single hash mod $10^4$ gives $\frac{1}{10000}$. So two small primes ($101,103$) already beat one modulus of $10^4$: $\frac{1}{10403}<\frac{1}{10000}$. Lesson: two independent moduli multiply their protection, which is why double hashing is so strong. See String Hashing for Substring Comparison.

$h(P)=0\cdot 26+1=1$. $P_{\text{high}}=26$. Codes of $T$: $b,a,b,a,b=1,0,1,0,1$.

• Window 0 "ba": $1\cdot 26+0=26$. $26\mathrm{mod}101=26\ne 1$ → skip.
• Roll → Window 1 "ab": drop b$=1$: $26-1\cdot 26=0$; slide+add b$=1$: $(0\cdot 26+1)=1$. $=1$ → verify "ab" ✓. Match at 1.
• Roll → Window 2 "ba": drop a$=0$: $1-0=1$; slide+add a$=0$: $(1\cdot 26+0)=26$. $\ne 1$ → skip.
• Roll → Window 3 "ab": drop b$=1$: $26-26=0$; slide+add b$=1$: $(0+1)=1$. $=1$ → verify ✓. Match at 3. Matches: indices 1 and 3. (Direct check: babab[1..2]=ab, [3..4]=ab. ✓)

Design:

1. Use double hashing: two random large primes $q_1,q_2\approx 10^9$, random bases $b_1,b_2$. Why: combined collision rate $\approx q_1^{-1}{q}_2^{-1}\approx 10^{-18}$ — even a crafted adversary cannot predict the random bases, so L3.3's collision attack fails.
2. Precompute $P_{\text{high}}=b^{m-1}\mathrm{mod}q$ once for each hash. Why: recomputing inside the loop makes each roll $O(\log m)$ and kills the speedup (the L2 precompute mistake at scale).
3. Guard subtraction with ((x)%q+q)%q. Why: prevents negative-hash corruption (L2 trap).
4. Still verify char-by-char on a (double) hash hit. Why: keeps correctness exact, and with double hashing verifications are essentially only on true matches, so expected time stays $O(n+m)$.
5. Fallback: if guaranteed worst-case $O(n+m)$ is mandated (e.g. hard real-time), switch to Knuth-Morris-Pratt or Z-Algorithm, which need no randomness.

Write $H_i={\sum }_{k=0}^{m-1}T[i+k]b^{m-1-k}$. The leading term is $T[i]b^{m-1}$. Drop: $H_i-T[i]b^{m-1}={\sum }_{k=1}^{m-1}T[i+k]b^{m-1-k}$. Slide ($\times b$): ${\sum }_{k=1}^{m-1}T[i+k]b^{m-k}$. Re-index with $j=k-1$: ${\sum }_{j=0}^{m-2}T[i+1+j]b^{m-1-j}$ — this is the hash of $T[i+\mathrm{1..}i+m-1]$ but missing its last character and with each weight one power too high... precisely, it equals the first $m-1$ terms of $H(T[i+\mathrm{1..}i+m])$. Add $T[i+m]b^0$: fills the final low-order digit, giving ${\sum }_{j=0}^{m-1}T[i+1+j]b^{m-1-j}=H(T[i+\mathrm{1..}i+m])$. ∎ Mod validity: addition, subtraction, and multiplication all commute with "$\mathrm{mod}q$" — that is a theorem of Modular Arithmetic. So doing every step mod $q$ gives the same remainder as computing the giant number first and reducing at the end. Division would not survive mod, which is why our hash uses only $+,-,\times$.

Rolling update formula ::: $H_{i+1}=((H_i-T[i]\cdot b^{m-1})\cdot b+T[i+m])\mathrm{mod}q$ Why keep verification after a double-hash hit? ::: To stay exactly correct; the rare/adversarial collision is the only thing between "probably equal" and "equal."