String Matching: Brute Force, KMP, Rabin-Karp

Hook #

Find a substring inside a larger string. It sounds trivial — just scan through, checking each position. That's the brute-force approach, and it's O(n × m) where n is the text length and m is the pattern length. For most production workloads, brute force is fast enough — that's what String#include? and strstr() typically do internally. But for very large text (DNA sequences, indexed search, log analysis), the brute force becomes the bottleneck. KMP and Rabin-Karp are the two most-cited algorithms that beat it, each via a clever insight. KMP avoids re-checking characters already matched; Rabin-Karp uses hashing to compare substrings in O(1). This lesson is about both, the trade-offs, and when to reach for them.

What you'll be able to do by the end of this lesson #

• Implement brute-force string matching in O(n × m).
• Implement KMP (Knuth-Morris-Pratt) in O(n + m) using a precomputed failure function.
• Implement Rabin-Karp in O(n + m) average case using a rolling hash.
• Predict which algorithm to use given the workload (single pattern vs many; pattern length; alphabet size).
• Recognise the failure-function intuition that makes KMP correct.

Why this matters here #

String matching appears in every text editor (find/replace), every search engine (substring queries), every grep / ripgrep / ag invocation, every IDE's symbol search, every bioinformatics tool (DNA pattern alignment), every spam filter, and every plagiarism detector. The standard library's String#index or strstr() is good enough for most code; the specialised algorithms matter when the workload is huge.

A second reason: KMP and Rabin-Karp are cleanly motivated — each one fixes a specific inefficiency of brute force. KMP fixes "we re-check characters we've already matched"; Rabin-Karp fixes "we compare m characters every time when we could compare a hash in O(1)." The two algorithms exemplify two general algorithm-design tactics — avoid redundant work and cheaper comparison via hashing.

We frame this lesson because MIT 6.006 and Abdul Bari cover the canonical content thoroughly. Our value-add is the when-to-use framing — the three algorithms aren't interchangeable.

The engineer's lens #

Three things the canonical resources teach but don't put a name on:

1. Brute force is the honest baseline — and surprisingly often the right choice. Walk through the text one position at a time; at each position, check whether the pattern matches.

rubydef brute_force_match(text, pattern)
  (0..text.length - pattern.length).each do |i|
    return i if text[i, pattern.length] == pattern
  end
  nil
end

Worst case: O(n × m). Example: text = "AAAAAAAB", pattern = "AAAAB". At each starting position, we compare 5 characters before finding the mismatch, then move one position right and repeat. n × m work.

In practice, the worst case rarely happens — natural text mismatches early, so the inner loop usually breaks after 1-2 character comparisons. Brute force is often O(n) amortised on real input. This is why strstr() in glibc is essentially brute force with some SSE tricks for the common case.

Production note: Ruby's String#index uses a slightly tuned brute force with shortcut tests. For most application code, brute force is the right choice and you don't need to switch.

2. KMP avoids re-checking matched characters via the failure function. The KMP insight: when a mismatch occurs after we've matched k characters of the pattern, we already know something about the text we just compared. Specifically, we know those k characters were the prefix of the pattern. KMP precomputes how much of that prefix could itself be a prefix-suffix overlap, and uses that to skip work.

The failure function for pattern P is an array f[i] = the length of the longest proper prefix of P[0..i] that is also a suffix of P[0..i].

For pattern "ABABAC": i: 0 1 2 3 4 5 P[i]: A B A B A C f[i]: 0 0 1 2 3 0

f[3] = 2 because "ABAB" has the longest proper prefix-suffix overlap "AB" of length 2.

The matching algorithm uses f to avoid restarting from scratch on mismatch. Total: O(n + m) — n for the text scan, m for failure-function preprocessing.

KMP's brilliance: the failure function captures the self-similarity of the pattern. The text-scan never needs to re-examine a character it's already compared. The proof of O(n) is one of the classical algorithm correctness proofs (CLRS 32.4).

When to use KMP: when you'll match the same pattern many times (preprocess once; reuse the failure function), or when worst-case latency matters more than average-case throughput.

3. Rabin-Karp uses hashing to compare substrings in O(1). The Rabin-Karp insight: instead of comparing m characters one-by-one at each position, compute a hash of the m-character window. If the hash matches the pattern's hash, then do the character-by-character check. Most windows have non-matching hashes, so the expensive comparison is rare.

The trick is the rolling hash: instead of recomputing the m-character hash from scratch at each position (which would be O(m) per position; back to O(n × m)), update the hash in O(1) by subtracting the leaving character and adding the entering character.

A common rolling hash is the polynomial hash:

texthash(s) = (s[0] × b^(m-1) + s[1] × b^(m-2) + ... + s[m-1]) mod p

where b is a base (e.g., 256 for byte strings) and p is a large prime. Sliding the window left by 1 position:

texthash(s[1..m]) = ((hash(s[0..m-1]) - s[0] × b^(m-1)) × b + s[m]) mod p

Constant-time update. Total: O(n + m) average; O(n × m) worst case (if every hash collides, which is astronomically unlikely with a good hash and a large prime).

When to use Rabin-Karp: when matching multiple patterns simultaneously (one hash per window, compared against many pattern hashes), or in scenarios where the hash trick generalises (Rabin's algorithm for 2D pattern matching uses the same idea on 2D windows).

The three-algorithm comparison #

There's also Boyer-Moore (skipped here — it scans the pattern right-to-left and uses skip heuristics; faster than KMP in practice for large alphabets like English text; CLRS Chapter 32.4 covers it).

For most application code, the standard library's brute force is fine. For grep / ripgrep, Boyer-Moore variants. For bioinformatics with DNA / RNA, KMP + suffix structures (Lesson 2). For multi-pattern matching, Aho-Corasick (a generalisation of KMP that handles many patterns at once).

What to focus on in the canonical resources #

• MIT 6.006 string-matching lecture — Rabin-Karp + KMP + correctness proofs. ~75 minutes.
• Abdul Bari's two videos (KMP and Rabin-Karp) — ~60 minutes total. The KMP failure-function trace is the load-bearing visual.
• Visualgo — 5 minutes to see all three algorithms run on the same input.
• CLRS Chapter 32 — read after MIT for the rigorous version. Boyer-Moore is in 32.4.
• What to skip on first pass — Aho-Corasick, suffix automaton. Specialised; cover when needed.
• What to come back to later — Boyer-Moore (skip heuristics for natural text), Z-algorithm (KMP cousin). All are useful but the three algorithms here are the foundation.

What to come back with #

Three predictions:

1. Run brute force vs KMP by hand. On text "ABABCABABABAC" and pattern "ABABAC":

   • How many character comparisons does brute force do (worst case)?
   • How many does KMP do (using its failure function)?

2. Compute the failure function. For pattern "AABAAC", what's f[i] for each position?

3. Choose the algorithm. For each scenario, pick brute force, KMP, or Rabin-Karp: a. Searching for "TODO" in a single source file. b. Matching a single regex pattern against a 10GB log file. c. Finding any of 1000 known-malicious URL patterns in incoming HTTP requests. d. Finding a specific DNA subsequence in a 3-billion-base human genome.

Where this connects #

Backward: Course 2.3 lesson 1 (hash functions) gave you the foundation for Rabin-Karp's rolling hash. Course 2.1 lesson 1 (arrays + static and dynamic) is the memory model underneath every string. Course 3.2 lesson 4 (binary search) is the other application of "compare in O(1)" via sorted data.

Forward: Lesson 2 (tries + suffix structures) generalises to preprocessed string data structures — when you'll query the same text many times. Lesson 3 (P vs NP) is the start of the theoretical half of the course. Course 13.x (NLP / Information Retrieval, if your path includes it) returns to string algorithms for tokenisation, search indexing, edit distance variations.

The zc-autocomplete-engine project for this course uses tries (Lesson 2). The string-matching algorithms here are the foundation for any text-search work you do.