String algorithms: KMP & rolling hash

The problem

The obvious search throws away what it already read

To find a pattern of length m in a text of length n, the obvious way lines the pattern up at each position and compares letter by letter. On a text like aaaaaaaab and the pattern aaab, almost every position matches several letters before failing, then the search shifts by one and compares most of them again. That is O(n × m) in the worst case.

Two ideas avoid the repeat work:

KMP studies the pattern first, so that after a mismatch it knows how much of the match it can keep. The text pointer only moves forward: O(n + m).
A rolling hash turns each window of the text into a number and updates it in O(1) as the window slides, so most positions are rejected by comparing one number. The search built on it is called Rabin-Karp.

The rule

Never move back in the text: either remember how much of the pattern still matches after a mismatch (KMP, at most 2n comparisons), or summarize each window in a number you can update in O(1) (rolling hash).

Basic

The failure function: how much of a match survives a mismatch

A proper prefix of a string is a prefix that is shorter than the whole string. The failure function of a pattern gives, for each position i, the length of the longest proper prefix of p[0..i] that is also a suffix of it. For aabaaab at position 6, the prefix aab is also the suffix aab, so the value is 3.

Why it matters: if the search has matched aabaaa and the next letter fails, those last letters are still a match for a shorter piece of the pattern, the one the table names. The search keeps that piece and carries on, instead of starting over.

The table is built with the same idea, matching the pattern against itself. k is the length of the current prefix match. When the next letter extends it, k grows by one. When it doesn't, k falls back to the next shorter prefix that still matches, fail[k − 1], and tries again.

k grows by at most one per letter and every fallback lowers it, so all the fallbacks together cost at most m: O(m) for the table. Its last value answers a problem of its own: the longest prefix that is also a suffix.

Medium

KMP search: the text pointer never moves back

The search runs the same loop over the text. k counts how many pattern letters match so far. A matching letter grows k; a mismatch lets k fall back through the failure table, never re-reading the text. When k reaches m, the pattern ends at the current letter.

Each text letter is read once and the fallbacks are paid for by earlier growth, so the search is O(n) after the O(m) table: O(n + m) in the worst case, with no false matches.

Hard

A rolling hash slides a window in O(1)

Read a window of L letters as a number in base B: c₀ × B^(L−1) + c₁ × B^(L−2) + … + c(L−1), where each c is a letter's code. Keep only the remainder mod a modulus M, so the number stays small. That is a hash function for windows, and sliding the window by one letter takes three operations:

remove the outgoing letter: subtract c₀ × B^(L−1);
shift: multiply by B;
add the incoming letter's code;

all mod M. Equal windows always get equal hashes. Different windows can collide, so an equal hash only means "maybe": compare the letters before trusting it.

The example finds the longest substring that appears twice. If a repeat of length L exists, one of every shorter length exists too, so Binary search on the answer picks the length, and for each length a rolling hash checks every window against a hash table of the hashes seen so far. The walkthrough uses M = 47 so that a collision actually happens; real code uses a modulus near 10⁹, or two different moduli, to make false alarms rare.

Each length costs one O(n) pass on average, plus a letter-by-letter check per hit, and the binary search tries O(log n) lengths: O(n log n) expected time.

Which one

KMP for guarantees, hashing for flexibility

	KMP	Rolling hash
Time for one pattern	O(n + m), worst case	O(n + m) expected; a bad hash can make it slower
False matches	None	Possible: verify every hit
Extra memory	The table, O(m)	O(1) for one pattern
Many patterns of one length, or comparing any two substrings	Awkward	Natural: put window hashes in a hash table

Most languages' built-in substring search is fast enough for everyday use; these two matter when the input is adversarial, very large, or the question is about repeats rather than a single pattern.

Check yourself

3 questions

1. The failure table of abab is [0, 0, 1, 2]. What does the last value, 2, say?

2. Two windows have the same rolling hash. What do you know?

3. Why is KMP O(n + m) even though its inner loop can fall back several times for one letter?

Takeaways

Remember this

The obvious search is O(n × m) because it re-reads text after each failed alignment.
The failure function stores, for each pattern position, the longest proper prefix that is also a suffix; KMP falls back through it and never moves back in the text.
A rolling hash updates a window's hash in O(1) by removing the outgoing letter, shifting and adding the incoming one, all mod M.
Hash hits are only candidates: verify the letters, and use a large modulus so collisions are rare.

Practice

Now solve some yourself

Mixed with topics you have practiced 0 unlocked

4 more once you have practiced Hash tables & maps, Linear & binary search, Binary search on the answer. Play one of its examples to the end and solve one of its problems to unlock them.

Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.