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

Before you can read the parent note you must own eight small ideas. We introduce them in order: each one uses only the ones before it. Nothing here assumes you have seen strings-as-numbers, modular arithmetic, or hashing before.

1. A string and its characters

Picture it. Look at the top row of the figure below: the word a b c sits in boxes numbered $0,1,2$. That box number is called the index.

• $s$ = the whole string.
• $s_i$ = the character sitting in box number $i$.
• The very first character is $s_0$, not $s_1$. Programmers count from zero — get used to it now, because every formula in the parent note does.

Why the topic needs this. The hash formula reads the string one box at a time, from the very first character $s_0$ onward. If you don't know what $s_i$ means, the whole formula is noise. (How many boxes there are — the length — we name in step 2.)

2. Length symbols $n$ and $m$

Picture it. In the figure above, the long strip is $T$ (length $n$) and the short strip is $P$ (length $m$). We slide $P$ along $T$ looking for a spot where they match.

Now we can pin down step 1 precisely: the pattern's characters run from $s_0$ up to $s_{m-1}$ — exactly $m$ boxes.

Why the topic needs this. The whole promise of Rabin-Karp is speed measured as "$O(n+m)$" — you literally cannot read that promise without knowing what $n$ and $m$ count. (What "$O(\cdot )$" means comes in step 8.)

3. Character codes — turning letters into digits

In the parent's tiny example the codes were $a=0,b=1$. In real code they use each letter's ASCII value (e.g. a = 97). The exact scheme doesn't matter; what matters is that each character now is a number we can compute with.

Picture it. The bottom row of the figure in step 1 shows each letter replaced by its code number, sitting under its box.

Why the topic needs this. The polynomial hash $H(s)=s_0{b}^{m-1}+\dots$ treats each $s_i$ as a number. That only makes sense once every character has a code.

4. A "window" sliding over the text

Picture it. Below, a red frame of width $m$ sits on the text. Slide it one box to the right and you get the next window.

• $T[i..i+m-1]$ = the characters $T[i],T[i+1],\dots ,T[i+m-1]$.
• The two dots .. mean "from here to there, inclusive."

How many windows are there? If the pattern fits ($m\le n$), the frame can start at index $0$ and its last legal start is $n-m$, giving $n-m+1$ positions. If the pattern is longer than the text ($m>n$), the frame simply doesn't fit anywhere, so there are zero windows and the answer is "no match" before we even hash. Always check this edge case first.

Why the topic needs this. Rabin-Karp compares the pattern against one window at a time. The rolling-hash magic is all about updating cheaply when this red frame slides by one.

5. Base-$b$ place value — the heart of the hash

Picture it. The figure below stacks a decimal number and a string side by side. Under each slot sits its multiplier: $\dots ,b^2,b^1,b^0$ for the string; $\dots ,100,10,1$ for the decimal. Same skeleton, different base.

So for a string $s$ of length $m$ we write its raw polynomial value as a capital $H$:

Read it slowly. The first character $s_0$ is multiplied by the biggest power $b^{m-1}$; the last character $s_{m-1}$ is multiplied by $b^0=1$. This is why swapping two letters usually changes the number — position carries weight.

Why the topic needs this. This polynomial is the raw hash value $H(s)$. Everything downstream — the rolling update, the collision talk — is arithmetic on this one expression. In step 6 we shrink $H(s)$ with a mod to get the value we actually store. See Hashing and String Hashing for Substring Comparison for where this same idea reappears.

6. Modular arithmetic — clock math and the prime $q$

Picture it. The clock figure below has $q$ marks. Counting past the top wraps around — that wrap-around is exactly what "mod" does. The red hand shows where $x=14$ lands on a $q=12$ clock: at $2$.

Three facts we lean on — the first two justify shrinking at every step, the third keeps us positive:

• Add-mod: $(a+b)\mathrm{mod}q=((a\mathrm{mod}q)+(b\mathrm{mod}q))\mathrm{mod}q$. You may take the mod early on each piece and still get the right final answer.
• Multiply-mod: $(a\cdot b)\mathrm{mod}q=((a\mathrm{mod}q)\cdot (b\mathrm{mod}q))\mathrm{mod}q$. This is the one that makes the rolling hash legal: the roll multiplies by the base $b$, and this rule says we can keep everything reduced mod $q$ through that multiplication without the numbers ever blowing up.
• Subtraction can go negative (e.g. $3-5=-2$). On a clock, $-2$ is the same spot as $q-2$. So to keep the result in the range $[0,q)$ we compute, in code, ((x) % q + q) % q — take the remainder, nudge it up by $q$ so it can't be negative, then take the remainder again.

Why the topic needs this. Without $\mathrm{mod}q$ the numbers are unstorable. With a tiny $q$ you get collisions everywhere (a parent-note mistake!). The prime $q$ is the dial that trades collision-safety against number size, and the multiply-mod rule is what makes the $O(1)$ roll possible at all.

7. Hash and collision

The golden rule this forces:

• Different hashes $\Rightarrow$ strings are definitely different (safe to skip).
• Same hashes $\Rightarrow$ strings are probably equal — you must verify character by character.

Why the topic needs this. Verification is not optional decoration; it is the safety net that turns "probably a match" into "certainly a match."

8. Big-O notation $O(\cdot )$

Picture it in your head. $O(1)$ is a flat line, $O(m)$ is a straight slope, $O(nm)$ is a steep curve. Rabin-Karp's whole selling point is turning the naive $O(nm)$ into an expected $O(n+m)$.

Why the topic needs this. Every claim in the parent note — "$O(1)$ update", "$O(n+m)$ expected", "$O(nm)$ worst case" — is written in this language. The rival methods Knuth-Morris-Pratt and Z-Algorithm are compared using the same yardstick.

How these feed the topic

Follow the arrows into the parent topic and every symbol there will already be yours.

Equipment checklist

Cover the right side and see if you can answer each before revealing.