# String Matching: KMP and Rabin-Karp Without the Mysticism > String matching without mysticism: derive KMP's failure function, Rabin-Karp's rolling hash with honest collision math, and the four LeetCode classics. Canonical: https://ironclad.academy/dsa/techniques/string-matching | Difficulty: advanced | Topics: String Matching, KMP, Rabin-Karp, Rolling Hash, Strings ## Key takeaways - The failure function answers exactly one question: after a mismatch, what is the longest proper prefix of the pattern that is also a suffix of what I just matched? Nothing else. - KMP never moves the text pointer backwards — the pattern position falls back through lps values instead, and the amortized argument caps total comparisons at 2n. - Rabin-Karp is "compare hashes, verify on collision" — the rolling update makes each slide O(1), and skipping the verify step turns your solution into a lottery ticket. - Use modulus 2^61 − 1 when comparing windows against each other: at 3 × 10^4 windows, 10^9 + 7 expects ~0.45 collisions per run; the Mersenne prime expects ~2 × 10^-10. - One failure-function array solves three LeetCode problems: LC 28 (search), LC 459 (repetition iff lps[-1] > 0 and n % (n − lps[-1]) == 0), LC 214 (lps of s + "#" + reversed s finds the longest palindromic prefix). - In production you call str.find or grep — two-way and Boyer-Moore beat both algorithms on real text. Rolling hashes are what actually ship, in rsync and dedup chunking. > **In one line:** KMP fixes naive string matching by remembering what it already matched — the failure function is just "longest proper prefix that is also a suffix" — while Rabin-Karp fixes it by comparing O(1) rolling hashes and verifying only on collision. The naive substring scan is O(n·m) because after a mismatch it slides the pattern by one and re-reads text it has already seen. Both classic fixes attack that waste, from opposite directions. KMP observes that the characters you just matched are known — so a precomputed table (the **failure function**) tells you exactly how far the pattern can shift without skipping a possible match, and the text pointer never moves backwards. Rabin-Karp observes that comparing two length-m strings costs O(m) — but comparing two hashes costs O(1), and a **rolling hash** updates in O(1) as the window slides. ```mermaid flowchart LR A["mismatch after\nmatching j chars"] --> B{"which fix?"} B -->|"naive: neither"| C["slide by 1, restart at\npattern position 0 —\nre-reads known text"] B -->|"KMP"| D["jump to lps[j-1],\ntext pointer never\nmoves back"] B -->|"Rabin-Karp"| E["never matched chars\nat all — compared one\nhash, slid in O(1)"] style C fill:#dc2626,color:#fff style D fill:#22c55e,color:#111 style E fill:#0e7490,color:#fff ``` **The core facts:** - `lps[i]` = length of the longest proper prefix of `pattern[0..i]` that is also a suffix of it. Build in O(m), search in O(n), at most 2n comparisons. - Rabin-Karp: polynomial hash mod a prime, slide in O(1), verify every hash match character-by-character. Expected O(n + m), worst O(n·m) under collisions. - Modulus choice is real math, not folklore: 2^61 − 1 for window-vs-window comparisons, because 10^9 + 7 expects ~0.45 collisions at n = 3 × 10^4. - Production code calls `str.find` (two-way algorithm) or grep (Boyer-Moore). The interview value is the invariant; the shipping value is the rolling hash (rsync, dedup). | Situation | Reach for | |---|---| | Single pattern, need worst-case guarantee or streaming text | KMP | | Pattern structure problems (periods, palindromic prefixes) | KMP failure function | | Substring-equality queries, binary-search-on-answer, many same-length patterns | Rolling hash | | Production substring search | The library (`str.find`, grep) | **If you have 60 seconds, say this.** Naive matching is O(n·m) because it forgets. KMP precomputes, for every pattern prefix, the longest proper prefix that is also a suffix — so after a mismatch it falls back to that length instead of restarting, the text pointer never retreats, and an amortized argument bounds the whole search at 2n comparisons. Rabin-Karp instead hashes each window with a polynomial rolling hash that updates in O(1) per slide, compares hashes, and verifies matches character-by-character — expected linear, but adversarial collisions degrade it to O(n·m), which is why you verify and why you pick a big modulus. In production you call the library; in interviews you explain the invariant. 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](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm), which Morris and Pratt described in a 1970 technical report and the three authors published jointly in 1977, and [Rabin-Karp](https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm), 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. [Interactive visualizer on the original page: array — pattern "ababaca" — one cell per character] [Interactive visualizer on the original page: array — lps for "ababaca" — longest proper prefix that is also a suffix, at each position] 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`. ```mermaid 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. ```python 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](/dsa/techniques/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`: ```python 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](/dsa/techniques/sliding-window) — the window state updates incrementally instead of being recomputed. ```python 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 ``` ```mermaid 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](/dsa/structures/hash-table) (or a [Bloom filter](/dsa/structures/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](/dsa/structures/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](/dsa/structures/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*. ```python 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. ```python 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 ``` ```mermaid 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](/dsa/techniques/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: ```python 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](https://github.com/python/cpython/blob/main/Objects/stringlib/stringlib_find_two_way_notes.txt) — 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](https://rsync.samba.org/tech_report/node3.html) 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](/dsa/crash-course/07-hashing), 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. ## Frequently asked questions Q: What does the KMP failure function actually store? A: For each position i in the pattern, lps[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix of it. That is the whole definition. After a mismatch at pattern position j, the longest chunk of what you just matched that could still be the beginning of a match is pattern[0..lps[j-1]-1], so you resume comparing at position lps[j-1] without ever moving the text pointer backwards. Building the table is O(m); searching is O(n) with at most 2n character comparisons. Q: Why is KMP O(n + m) despite the nested while loop? A: Amortization. The pattern position j increases at most once per text character, so at most n times total. Every iteration of the fallback loop strictly decreases j, and j never goes below 0 — so the total number of fallback steps across the entire run is bounded by the total number of increases, which is n. That caps the search at roughly 2n comparisons, plus O(m) to build the failure function with the same argument applied to the pattern. Q: How does the Rabin-Karp rolling hash work? A: Treat each length-m window of the text as an m-digit number in base B, reduced mod a prime p: h = (c₀·B^(m−1) + c₁·B^(m−2) + … + c_{m−1}) mod p. Sliding the window one position right is O(1): subtract the outgoing character times B^(m−1), multiply by B, add the incoming character, all mod p. When a window hash equals the pattern hash you verify character-by-character, because hashes can collide. Expected running time is O(n + m); the worst case is O(n·m). Q: Why does Rabin-Karp degrade to O(n·m) in the worst case? A: Every hash match triggers an O(m) character-by-character verification. If many windows collide with the pattern hash, you pay that verification at almost every position — n verifications of m characters each is O(n·m). Random text essentially never does this, but an adversary who knows your base and modulus can construct input that does; competitive-programming judges see exactly these "anti-hash" attacks. Choosing the base randomly at runtime makes the attack impractical. Q: Which modulus should I use for a rolling hash? A: Use the Mersenne prime 2^61 − 1 (or two independent smaller mods). The birthday bound is the reason: comparing all windows of a 30,000-character string against each other is about 4.5 × 10^8 pairs, and with p = 2^61 − 1 the expected number of colliding pairs is around 2 × 10^-10 — effectively never. With the popular p = 10^9 + 7 the same arithmetic gives about 0.45 expected collisions, close to a coin flip per run. For a single pattern against n windows (plain substring search) even the small prime is fine; the big modulus matters when you compare windows against each other, as in Longest Duplicate Substring. Q: Should I ever implement KMP in production code? A: Almost never. CPython's str.find uses the Crochemore-Perrin two-way algorithm (linear worst case, O(1) space) layered with a Boyer-Moore-style skip table, and GNU grep uses Boyer-Moore with an unrolled inner loop — both beat a hand-rolled KMP on real text. The interview value of KMP is the invariant reasoning, not the code. Rolling hashes are the part that ships: rsync's weak/strong checksum pair and content-defined chunking in dedup systems are Rabin-Karp's compare-then-verify idea at file scale.