String Matching: KMP and Rabin-Karp Without the Mysticism

Here is the exact moment naive string matching wastes work. Your pattern is "ababaca". You have matched five characters against the text — a b a b a — and the sixth comparison fails. The naive algorithm slides the pattern one position right and starts over from the pattern's first character, re-reading text it has already seen. But it knows what those characters are. It matched them two microseconds ago. Restarting from scratch throws away five characters of hard-won information, and the whole O(n·m) worst case is that theft compounding.

How bad does the compounding get? On random text, barely at all — mismatches happen on the first or second character and the naive scan is effectively linear. On repetitive input it is a disaster:

Naive worst case:
  haystack = "a" × 10,000        needle = "a" × 4,999 + "b"
  alignments to try:   10,000 − 5,000 + 1 ≈ 5,000
  compares per align:  ~5,000  (mismatch only at the final char)
  total ≈ 25,000,000 character comparisons
       — milliseconds in C, seconds in a char-by-char Python loop

KMP on the same input: ≤ 2 × 10,000 = 20,000 comparisons.
About 1,000× less work. Same answer.

Repetitive input is not exotic. DNA sequences, log files, JSON with deeply repeated keys — real data is full of near-periodic runs. And in an interview, "what's your worst case?" is the first follow-up. This article builds both classic answers from that single observation about wasted information: Knuth-Morris-Pratt, which Morris and Pratt described in a 1970 technical report and the three authors published jointly in 1977, and Rabin-Karp, which Karp and Rabin published in 1987. Neither is magic. Each answers one question well.

The question the failure function answers

Freeze the mismatch moment. You matched pattern[0..j-1] — call it the matched region — and pattern[j] failed. The naive scan restarts at the next alignment. KMP instead asks: of all the alignments I would otherwise try one at a time, which is the nearest one that could possibly still match, given what I know the text says?

Any such alignment overlaps the matched region. For the pattern to survive that overlap, the part of the pattern that lands on the tail of the matched region has to equal that tail. But the matched region is pattern[0..j-1] — that's what "matched" means. So the survivable alignments are exactly the ones where a proper prefix of the pattern equals a suffix of pattern[0..j-1]. The nearest alignment corresponds to the longest such prefix. That is the entire failure function:

lps[i] = the length of the longest proper prefix of pattern[0..i] that is also a suffix of pattern[0..i].

("Proper" means not the whole string — otherwise every entry would trivially be i + 1.) After a mismatch at pattern position j, you resume comparing at position lps[j-1]. The first lps[j-1] characters are already known to match, because they are a prefix of the pattern that equals the tail of what you just matched. The text pointer does not move backwards. Ever.

{ "type": "array", "title": "pattern \"ababaca\" — one cell per character", "data": ["a", "b", "a", "b", "a", "c", "a"] }

{ "type": "array", "title": "lps for \"ababaca\" — longest proper prefix that is also a suffix, at each position", "data": [0, 0, 1, 2, 3, 0, 1] }

Check one entry by hand: at index 4 the prefix so far is "ababa". Its proper prefixes are a, ab, aba, abab; its suffixes include a, ba, aba, baba. The longest string in both lists is "aba", length 3 — so lps[4] = 3. At index 5 ("ababac"), nothing ending in c matches any prefix, so lps[5] = 0.

flowchart TB
    A["matched 'ababa' (j = 5), then text char 'b' ≠ pattern[5] = 'c'"] --> B["lps[4] = 3 — the longest prefix of 'ababa'\nthat is also its suffix is 'aba'"]
    B --> C["shift so the pattern's first 3 chars sit under\nthe last 3 matched chars — they already agree,\nso resume comparing at pattern[3]"]
    style A fill:#1e3a5f,color:#e2e8f0
    style B fill:#0e7490,color:#fff
    style C fill:#22c55e,color:#111

Why is it safe to jump straight to the longest one instead of trying every alignment in between? Suppose some skipped alignment actually led to a match. Then at that alignment a prefix of the pattern equals a suffix of the matched region — but that prefix would be longer than lps[j-1], contradicting "longest." The jump cannot skip a real match. That one-sentence proof is what interviewers are fishing for when they ask "why doesn't KMP miss matches?"

Building the table in O(m)

The build is the search applied to the pattern itself: for each new character, extend the current longest prefix-suffix if you can, and if you can't, fall back — using the table you've built so far.

def build_lps(pattern: str) -> list[int]:
    m = len(pattern)
    lps = [0] * m
    k = 0                                  # length of current longest prefix-suffix
    for i in range(1, m):
        while k > 0 and pattern[i] != pattern[k]:
            k = lps[k - 1]                 # fall back to the next-longest candidate
        if pattern[i] == pattern[k]:
            k += 1
        lps[i] = k
    return lps

The subtle line is k = lps[k - 1]. When pattern[i] fails to extend the current candidate prefix of length k, the next candidate is not k - 1. It is the longest prefix-suffix of that prefix — which is exactly what lps[k - 1] stores. The candidates form a chain, and you ride it down until something extends or you hit zero. Watch it on "ababaca" at i = 5 ('c'): k is 3, pattern[3] = 'b' ≠ 'c', fall to lps[2] = 1; pattern[1] = 'b' ≠ 'c', fall to lps[0] = 0; pattern[0] = 'a' ≠ 'c', and k stays 0. Three probes, not a rescan of the whole prefix.

Why is this O(m) when there's a while-loop inside a for-loop? Amortization. k increases at most once per iteration of the for-loop — at most m − 1 times total. Every trip through the while-loop strictly decreases k, and k never goes negative. You cannot descend more than you climbed, so total fallback steps ≤ total increments ≤ m. The same argument you've seen for the pop-while loop in a monotonic stack: count total movement across the whole run, not per-iteration cost.

The search loop

Search is the same loop, run over the text, with the pattern position j playing the role of k:

def kmp_search(haystack: str, needle: str) -> int:
    if not needle:
        return 0
    lps = build_lps(needle)
    j = 0
    for i, ch in enumerate(haystack):
        while j > 0 and ch != needle[j]:
            j = lps[j - 1]
        if ch == needle[j]:
            j += 1
        if j == len(needle):
            return i - j + 1               # first match; use j = lps[j-1] here to find all
    return -1

The loop invariant carries the correctness proof: after processing haystack[i], j is the length of the longest prefix of the needle that is a suffix of haystack[0..i]. When j hits m, a full copy of the needle ends at position i. The text index i moves forward monotonically — this is why KMP works on streams you can't rewind, like a network socket — and the same amortized argument bounds everything at roughly 2n character comparisons. O(n + m) total, O(m) extra space for the table.

Trace the interesting step on haystack = "abababaca", needle = "ababaca". By i = 4 you've matched "ababa" (j = 5). At i = 5 the text char is 'b' but needle[5] = 'c': fall back to j = lps[4] = 3, compare 'b' against needle[3] = 'b' — match, j = 4. The prefix "aba" was silently reused without touching the text again, and the full match completes at index 2 a few steps later.

Rabin-Karp: compare hashes, verify on collision

KMP is one fix. The other is to stop comparing strings entirely. Comparing two length-m windows costs O(m), but comparing two 64-bit numbers costs O(1) — so fingerprint every window and only do the O(m) comparison when fingerprints agree. For this to beat naive, computing each window's fingerprint must not itself cost O(m). That's the rolling hash.

Treat a window as an m-digit number in base B, reduced mod a prime p:

h(s[i..i+m-1]) = ( s[i]·B^(m−1) + s[i+1]·B^(m−2) + … + s[i+m−1] ) mod p

Slide the window one step right and the new hash is one subtraction, one multiplication, one addition: drop the outgoing character's s[i]·B^(m−1) term, shift everything up by multiplying by B, append the incoming character. O(1) per slide, like the running counters in a sliding window — the window state updates incrementally instead of being recomputed.

def rabin_karp(haystack: str, needle: str) -> int:
    n, m = len(haystack), len(needle)
    if m == 0 or m > n:
        return 0 if m == 0 else -1
    B, P = 256, (1 << 61) - 1              # base > alphabet, Mersenne-prime modulus
    top = pow(B, m - 1, P)                 # B^(m-1) mod P, precomputed once

    h_needle = h_win = 0
    for i in range(m):
        h_needle = (h_needle * B + ord(needle[i])) % P
        h_win    = (h_win    * B + ord(haystack[i])) % P

    for i in range(n - m + 1):
        if h_win == h_needle and haystack[i:i + m] == needle:   # verify!
            return i
        if i + m < n:
            h_win = ((h_win - ord(haystack[i]) * top) * B
                     + ord(haystack[i + m])) % P
    return -1

flowchart LR
    W["window hash h(i)"] --> C{"h(i) == h(pattern)?"}
    C -->|"no"| S["slide — O(1)\nrolling update"]
    C -->|"yes"| V["verify char-by-char\nO(m)"]
    V -->|"equal"| F["match at i"]
    V -->|"collision"| S
    S --> W
    style V fill:#ffaa00,color:#111
    style F fill:#22c55e,color:#111
    style C fill:#a855f7,color:#fff

Two knobs matter. The base must exceed the alphabet size so distinct windows encode to distinct numbers before the mod — 256 for bytes is the lazy correct choice. (Mapping 'a' to 0 in base 26 is a classic bug: "aab" and "ab" hash identically because leading zeros vanish.) The modulus controls collisions, and the choice is arithmetic, not superstition:

Collision budget (birthday bound, illustrative):
  comparing all windows of a string, n = 3 × 10^4
  pairs ≈ n²/2 = 4.5 × 10^8
  expected colliding pairs ≈ pairs / p

  p = 10^9 + 7:      4.5×10^8 / 10^9      ≈ 0.45   — a coin flip per run
  p = 2^61 − 1:      4.5×10^8 / 2.3×10^18 ≈ 2×10^-10 — effectively never

  single pattern vs n windows (plain search): expected ≈ n / p
  even at p = 10^9 + 7 that is 3×10^-5. The big prime matters
  when windows are compared against EACH OTHER.

Average case O(n + m). Worst case O(n·m) — and it's worth being precise about when. Every hash match costs an O(m) verification. If many windows collide with the pattern hash, you verify at nearly every position, and n verifications × m characters is the naive scan with extra steps. Random text won't do this to you. An adversary will: anyone who knows your base and modulus can construct inputs whose windows all collide, and competitive-programming judges host exactly these anti-hash attacks against fixed-constant hashes. The defense Karp and Rabin actually proposed is randomization — pick the base (or modulus) randomly at runtime so no fixed input is bad on purpose. The degradation is real but a choice: verify and you're slow-but-correct in the worst case; skip verification and you're fast-but-wrong with some probability you now get to compute.

One genuine Rabin-Karp superpower before the worked problems: multiple patterns. Hash k same-length patterns into a hash table (or a Bloom filter when k is huge), then make one rolling pass over the text checking membership — expected O(n + k·m) versus O(k·n) for running KMP k times. Plagiarism detectors and content scanners live on this. For multi-pattern matching with different lengths, the right tool is Aho-Corasick, which is precisely KMP's failure-link idea built over a trie.

Worked problem 1: Find the Index of the First Occurrence (LC 28)

The canonical "implement strStr" problem: return the index of the first occurrence of needle in haystack, or −1. Constraints are small — both strings up to 10^4 characters, lowercase — so the naive scan passes. Which tells you what the problem is really for: writing KMP under interview conditions and explaining why it's O(n + m). The kmp_search above is a complete accepted solution. What separates candidates is the follow-up answers: why lps[j-1] and not lps[j] (you're asking about the region before the mismatch), why the text pointer never retreats (the invariant tracks the longest needle prefix ending at i), and why it's ≤ 2n comparisons (the amortized climb/fall argument). If you can state those three, the code is almost incidental.

Worked problem 2: Repeated Substring Pattern (LC 459)

Is s some substring repeated two or more times — "abab" yes, "aba" no? The failure function answers this with three lines, and the reason it can is the best illustration of what lps means.

def repeated_substring_pattern(s: str) -> bool:
    n = len(s)
    f = build_lps(s)[-1]          # longest proper prefix-suffix of the whole string
    return f > 0 and n % (n - f) == 0

Let f = lps[n-1] and d = n − f. Saying "the first f characters equal the last f characters" is saying the string overlaps itself at shift d: s[i] == s[i + d] for every valid i. So s is periodic with period d. If d divides n, the string is exactly n/d copies of its first d characters — a genuine repetition. If d doesn't divide n, the period doesn't tile the string evenly, and no shorter one works either (a full repetition of block length b would force lps[n-1] ≥ n − b, so d = n − f is the smallest period). Check "abab": lps is [0, 0, 1, 2], f = 2, d = 2, and 4 % 2 == 0 — true. Check "abaab": lps ends at 2, d = 3, 5 % 3 ≠ 0 — false. The failure function is secretly a period detector, which is why it shows up in string problems that have nothing to do with searching.

Worked problem 3: Shortest Palindrome (LC 214)

Prepend the fewest characters to s to make a palindrome. Equivalent form: find the longest prefix of s that is a palindrome, then prepend the reverse of whatever's left. The failure-function trick: a palindromic prefix of s is exactly a prefix of s that is also a suffix of reverse(s) — so build one string where "prefix of one, suffix of the other" is what lps measures.

def shortest_palindrome(s: str) -> str:
    if not s:
        return s
    t = s + "#" + s[::-1]          # "#" must not occur in s
    k = build_lps(t)[-1]           # length of longest palindromic prefix of s
    return s[k:][::-1] + s

flowchart LR
    S["s = 'aacecaaa'"] --> T["t = s + '#' + reverse(s)\n= 'aacecaaa#aaacecaa'"]
    T --> L["lps of t ends at 7 —\npalindromic prefix 'aacecaa'"]
    L --> R["prepend reverse of the rest —\n'a' + s = 'aaacecaaa'"]
    style T fill:#0e7490,color:#fff
    style R fill:#22c55e,color:#111

The "#" separator is load-bearing. It caps every prefix-suffix overlap at len(s), so lps can't claim an overlap longer than the original string. Drop it with s = "aaaa" and t = "aaaaaaaa" reports an overlap of 7 — nonsense, since the palindromic prefix can be at most 4. With the separator, k = 4, nothing gets prepended, and "aaaa" is correctly its own answer. O(n) time, and the whole solution is one failure-function build over a string of length 2n + 1.

Worked problem 4: Longest Duplicate Substring (LC 1044)

Find the longest substring occurring at least twice — LeetCode Hard, n in the tens of thousands, and naive enumeration of substrings is O(n³)-ish. The structure that saves you: if a duplicate of length L exists, duplicates of every shorter length exist too (take prefixes of it). "Exists a duplicate of length L" is monotone in L, so binary search the length. Checking one length L is where Rabin-Karp earns its place — hash all n − L + 1 windows with one rolling pass and look for a repeat in a set:

def longest_dup_substring(s: str) -> str:
    n = len(s)
    nums = [ord(c) for c in s]
    B, P = 256, (1 << 61) - 1

    def dup_start(L: int) -> int:          # start of a 2nd occurrence, else -1
        top = pow(B, L - 1, P)
        h = 0
        for i in range(L):
            h = (h * B + nums[i]) % P
        seen = {h: [0]}                    # hash -> starting indices
        for i in range(1, n - L + 1):
            h = ((h - nums[i - 1] * top) * B + nums[i + L - 1]) % P
            if h in seen:
                if any(s[j:j + L] == s[i:i + L] for j in seen[h]):
                    return i               # verified, not just hash-equal
                seen[h].append(i)
            else:
                seen[h] = [i]
        return -1

    lo, hi, best, best_len = 1, n - 1, -1, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        start = dup_start(mid)
        if start != -1:
            best, best_len, lo = start, mid, mid + 1
        else:
            hi = mid - 1
    return s[best:best + best_len] if best != -1 else ""

Expected O(n log n): log n binary-search steps, each an O(n) rolling pass. This is exactly the all-windows-against-each-other regime from the collision-budget block — the reason the code uses 2^61 − 1 and still verifies on hash hits. Most accepted solutions online skip verification with a 64-bit hash; they're gambling at odds of roughly 10^-10 per run, which happens to be a good bet, but say out loud in an interview that it is a bet and what the stake is. That sentence is worth more than the code.

What breaks

Skipping verification. The judge accepts your unverified Rabin-Karp; an adversarial input generator doesn't. Anti-hash tests that break fixed-constant hashes are a documented sport on competitive-programming platforms. Verify on hash match, or randomize the base per run, or both. In anything user-facing, always verify — "probably equal" is not a string comparison.

10^9 + 7 in the wrong regime. Fine for one pattern versus n windows (collision odds ~n/p ≈ 3×10^-5 at n = 3×10^4). A coin flip for window-versus-window problems like LC 1044 (~0.45 expected collisions, per the arithmetic above). The failure is intermittent — it passes your tests and fails one resubmission in two — which makes it the most annoying bug class in this article. Use 2^61 − 1 or double-hash.

Base smaller than the alphabet, or a character mapped to zero. "aab" and "ab" colliding because leading 'a's vanish in base 26 with 'a' → 0. Map to 1..26 or use base 256 and never think about it again.

Negative intermediate values in fixed-width languages. (h - out * top) * B goes negative before the mod. Python's % returns non-negative values; Java's and C++'s don't. Add p (or p²-scale slack) before reducing, or use unsigned 64-bit with a Mersenne-prime reduction. Porting working Python to Java and watching it fail on the third test is a rite of passage.

k = lps[k] instead of k = lps[k - 1]. The off-by-one that turns the fallback chain into an infinite loop or a wrong table. The mnemonic: you're asking about the prefix of length k, and information about it lives at index k − 1. Same story in the search loop with j.

Missing separator in the LC 214 trick. Without "#", lps of s + reverse(s) can exceed len(s) and you prepend garbage (the "aaaa" example above). Any character guaranteed absent from s works; the guarantee is the point, not the character.

Assuming KMP is fast in practice. It's safe, not fast. On random text the naive scan and library routines win — fewer branch mispredictions, SIMD memcmp, cache-friendly skips. KMP's value is the guarantee that no input, however hostile, makes it quadratic. If your benchmark is English prose and your baseline is str.find, hand-rolled KMP will lose, and that's expected.

Where string matching actually lives in production

You will probably never ship hand-written KMP, and the reasons are instructive. CPython's str.find uses the Crochemore-Perrin two-way algorithm — linear worst case like KMP but O(1) space — layered with a Boyer-Moore-style bad-character table for sublinear skipping on typical text, and it switches strategies adaptively based on observed comparison counts. GNU grep is built on Boyer-Moore, which reads the last character of each alignment first and skips whole windows on a miss — often not touching most input bytes at all. Against engineering like that, your 15-line KMP is a teaching aid. Calling the library is the correct production decision, and knowing why it wins is the interview decision.

The rolling hash is the half that ships. rsync's delta-transfer algorithm computes a cheap 32-bit rolling checksum (inspired by Adler-32: a byte-sum and a position-weighted sum) at every offset of a file, and only when the weak checksum matches a block does it compute a strong hash to confirm — compare cheap fingerprints, verify on collision, at file-sync scale. Content-defined chunking in dedup and backup systems runs a rolling hash over the byte stream and cuts a chunk boundary wherever the low-order bits hit a target value, so an insertion early in a file doesn't shift every later chunk boundary — the design that came out of the LBFS line of work, with faster modern variants (Gear, FastCDC) keeping the same shape. Same skeleton as the hashing you already know, applied to a sliding window instead of a key.

The decision in practice

	Preprocess	Search	Space	Reach for it when
Naive scan	—	O(n·m) worst, ~O(n) random text	O(1)	n·m is small and clarity wins code review
KMP	O(m)	O(n) guaranteed	O(m)	worst-case guarantees, streaming input, period/prefix structure problems
Rabin-Karp	O(m)	O(n + m) expected, O(n·m) worst	O(1)	window-equality at scale, binary-search-on-answer, k same-length patterns
Two-way / Boyer-Moore (library)	O(m)	O(n) worst (two-way), sublinear typical (BM skips)	O(1)	production. Call str.find

For interviews, the split is clean. If the problem is "find this pattern" with a worst-case follow-up, or anything about a string's internal structure — repetition (LC 459), palindromic prefixes (LC 214), borders and periods — that's KMP territory, and the failure function is usually the entire solution. If the problem compares many windows for equality — longest duplicate (LC 1044), repeated DNA sequences, "do these two ranges match" queries — that's rolling-hash territory, and the skill being tested is whether you handle collisions honestly: verify on hash match, size the modulus with the birthday bound, and know the O(n·m) cliff exists.

For production, call the library and spend your judgment elsewhere. The two-way algorithm behind str.find gives you KMP's guarantee without KMP's constant factors, and grep will beat anything you write this month. What survives from this article into real systems is the invariant reasoning — "never re-read what you already know" shows up in every incremental computation you'll ever build — and the rolling hash, which is quietly moving your backups around right now.