String Matching: never re-check what you already know

01 · The baseline

The naive approach, and why it's slow

The most obvious way to find a pattern inside a text: line the pattern up against position 0 of the text, compare character by character until either the whole pattern matches or something disagrees, then slide the pattern one position to the right and start the comparison over from the pattern's first character. Repeat until the pattern has been tried at every possible starting position.

It's correct, and for small inputs it's fine. The problem is what happens when the text has a lot of partial matches that ultimately fail — which is exactly the case that shows up constantly in practice (repetitive text, DNA sequences, anything with a small alphabet).

Take pattern "AAAAB" against text "AAAAAAAAAAAB" (eleven A's, then a B). At shift 0, the naive method compares A,A,A,A — all match — then compares the 5th characters, B vs A — mismatch. It slides one position right and does the exact same thing: four matching A's, then a mismatch on the 5th. This repeats at every one of the first seven shifts, re-doing the same four comparisons every single time before finally succeeding at shift 7. Worst case, this is O(n·m) — for text length n and pattern length m — because in the worst case you redo almost the full pattern's worth of comparisons at almost every shift.

02 · The insight

KMP's insight — the pattern already told you something

When a mismatch happens partway through comparing the pattern against the text, you're not starting from nothing. You know exactly which characters just matched — they're sitting right there in the pattern itself. Knuth-Morris-Pratt (KMP) uses that fact: instead of sliding the pattern by one and re-comparing from its start, it jumps the pattern forward to the next position where the already-matched suffix of text could still line up with some prefix of the pattern — and it never re-compares a character in the text twice.

The jump distances are precomputed from the pattern alone, before the text is even scanned. This table is usually called the LPS array (Longest proper Prefix which is also a Suffix), or the "failure function." LPS[i] is the length of the longest proper prefix of the pattern (considering only pattern[0..i]) that is also a suffix of that same substring. "Proper" matters here — the prefix can't be the entire substring itself, only something shorter than it.

Here's the LPS array for pattern "ABABCABAB":

Read LPS[8] = 4 (outlined) as: the longest proper prefix of "ABABCABAB" that also appears as a suffix of it is "ABAB" — 4 characters, matching both the start and the end of the substring. Notice LPS[4] = 0: the substring up through C is "ABABC", and no proper prefix of it reappears as a suffix, because it ends in C and no prefix starts with C except the whole thing. If a mismatch occurs at pattern position 8 while scanning text, KMP doesn't restart — it knows the last 4 matched characters ("ABAB") already satisfy the first 4 characters of the pattern, so it resumes comparing from pattern position 4 instead of position 0.

03 · Method

A repeatable framework

1. 1 Build the LPS table firstFrom the pattern alone, before looking at the text at all. For each position i, LPS[i] is the length of the longest proper prefix of the pattern (up to i) that is also a suffix ending at i.
2. 2 Scan with two pointersOne pointer walks the text, the other walks the pattern. Compare the characters they currently point to.
3. 3 On a match, advance bothMove the text pointer and the pattern pointer forward together and keep comparing.
4. 4 On a mismatch, don't restart the text pointerUse the LPS table to move the pattern pointer back to the right spot instead — skipping only the part of the pattern you'd re-match anyway. The text pointer never moves backward.
5. 5 On a full match, record it and keep goingTo find all occurrences (not just the first), fall the pattern pointer back using the LPS table — same as a mismatch — rather than resetting it to 0, so overlapping matches aren't missed.

04 · Building the table

How the LPS table itself gets built

Building the LPS table uses the exact same "don't redo work" idea it's meant to provide, just applied one level down — to the pattern comparing against itself. Two pointers do the work: i scans forward through the pattern, and len tracks the length of the current matched prefix.

This is why the table has to be finished in full before the text scan begins: the fallback for position i depends on earlier LPS values already being correct.

05 · Complexity

Why KMP is O(n + m), not O(n·m)

Building the LPS table costs O(m) — the len pointer only ever moves forward overall, even with its fallbacks, so building the table touches each pattern position a bounded number of times. Scanning the text costs O(n) for the same reason: the text pointer never moves backward, and the pattern pointer's fallbacks are bounded by how far it previously advanced. Add them together: O(n + m) total, versus naive search's worst case of O(n·m).

The intuitive way to see it: every character in the text is examined an amortized constant number of times overall, across the entire scan — not once per pattern position, as in the naive approach.

06 · Context

Other string-matching approaches

KMP isn't the only tool for this problem. Rabin-Karp takes a different route: it hashes the pattern once, then slides a rolling hash across the text so each candidate window can be compared in roughly O(1) after preprocessing — this makes it a good fit for searching many patterns at once, though hash collisions mean a "match" from the hash still needs a direct character check to confirm. The Z-function is a close cousin of KMP's failure function — instead of "prefix matching suffix," it computes, for every position in a string, the length of the longest substring starting there that matches a prefix of the whole string, which solves a closely related family of pattern-matching problems with similar linear-time guarantees.

07 · Before you start coding

Common mistakes

• Confusing "proper prefix that's also a suffix" with just "any prefix" — the prefix must be strictly shorter than the substring itself, or the LPS value is meaningless.
• Off-by-one indexing when building or reading the LPS table — mixing up whether LPS[i] describes the substring ending at i inclusive or exclusive is the most common source of bugs.
• Starting the text scan before the LPS table is fully built — the fallback logic depends on every earlier entry already being correct.
• Resetting the fallback pointer to 0 on every mismatch during LPS construction, instead of falling back to the previous LPS value — this silently degrades performance back toward brute-force behavior.
• Resetting the pattern pointer to 0 after finding a full match while searching for all occurrences — overlapping matches get missed. Use the LPS table for that fallback too, just like an ordinary mismatch.

08 · Try it

See it in action

One visualizer covers this family so far — watch the LPS table build, then watch the two pointers move through a real search.