String matching beyond brute force

The question is simple: does a small string (the pattern, call it P) appear somewhere inside a bigger string (the text, call it T)? The obvious way is to line P up at position 0 of T, compare character by character, and if anything mismatches, slide P over by one and start the comparison over from scratch. With T of length n and P of length m, that re-checking can cost up to O(n·m) — for every one of the n starting spots you might re-scan all m characters. The two methods here, KMP and Rabin-Karp, both get you to O(n+m): they avoid redoing work.

Analogy for KMP: imagine you're looking for the word "ababa" in a long sentence, reading left to right, and you've already matched "abab" before hitting a wrong letter. The naive reader throws all that progress away and restarts one letter later. But you're smarter — you notice the "ab" at the end of what you matched is the same as the "ab" at the start of the pattern, so you don't need to re-read those; you can keep that partial credit and continue. KMP precomputes exactly how much partial credit you keep at each point. That precomputed table is the failure function (the array fail in the code).

Definition, slowly: fail[i] is the length of the longest proper prefix of P[0..i] that is also a suffix of it. "Prefix" = a chunk starting at the front. "Suffix" = a chunk ending at the back. "Proper" = not the whole string itself. So it answers: "of the first i+1 characters I've matched, how many characters at the front also appear, identically, at the back?" That overlap is what lets us slide the pattern forward without rescanning. Now let's trace kmp_failure on the tiny pattern P = "ababa". The variable k tracks the current overlap length. We start fail[0] = 0 (a single character has no proper prefix), then walk i from 1 to the end. The highlighted cell is the index i we're filling right now.

Why this is fast: in the search loop, k only goes up by 1 per character read, and each time we mismatch we shrink k via the failure table — never re-reading text characters. Total work is proportional to the length of the text plus the length of the pattern, i.e. O(n+m). The while k > 0 loop looks like it could be slow, but across the whole run it can only undo increments that already happened, so it's bounded overall.

The second method, Rabin-Karp, takes a totally different angle: turn each window of m characters into a single number (a hash), like reading the characters as digits of a base-257 number taken modulo a big prime M. Comparing two numbers is one O(1) step. As the window slides right one spot, you subtract the leaving character's contribution, multiply by the base, and add the new character — also O(1) — so you don't recompute the whole window. Because two different strings can occasionally land on the same number (a collision), whenever the hashes match you do one real character-by-character comparison (text[i:i+m] == p) to confirm it's a true match and not a coincidence. With a good prime, collisions are rare, so this averages O(n+m) too.