KMP String Matching
Hard+110 XPFind a pattern inside a text without ever re-checking characters you already matched, using the LPS table.
No visualization loaded.
Watch
—
Press Run to begin.
You want to find a small word (the 'pattern') inside a big piece of text. The obvious way is to line up the pattern at the start, compare letter by letter, and if something doesn't match, slide the pattern over by one and start comparing all over again. The problem: when you slide by one, you throw away everything you'd already matched and re-check letters you've seen. KMP fixes this. Before searching, it studies the pattern and builds a little cheat-sheet called the LPS table. The LPS table says, for each spot in the pattern, 'if you fail here, how many letters at the start of the pattern have you ALREADY matched, so you don't have to recheck them?' Using that, when a mismatch happens you jump the pattern forward smartly and — importantly — you NEVER move backward in the text. That's what makes it fast.
▸What does the LPS table actually store, and why does it help?
LPS stands for 'Longest proper Prefix which is also a Suffix.' For each position in the pattern, lps[k] is the length of the longest chunk that appears BOTH at the very start of pattern[0..k] and at its very end (but isn't the whole thing). Example: for 'ababa', after matching 'abab' the start 'ab' equals the end 'ab', so when we fail next we already know those 2 letters line up again — we can keep them instead of rechecking. The table is just those reusable overlaps precomputed once.
▸Why is the naive way wasteful?
The naive search re-compares characters it already looked at. Say the pattern is 'ababa' and the first four letters 'abab' matched the text, then the fifth fails. The naive method slides over by one and re-compares starting from the text character it ALREADY checked — wasting all that matched work. If the text is mostly the same letter, this re-checking piles up to about n×m comparisons (O(n·m)). KMP never re-reads a text character it already passed.
▸How does the LPS let you 'skip ahead without going back in the text'?
When a mismatch happens at pattern position j, KMP doesn't rewind the text pointer i at all. Instead it sets j back to lps[j-1] — the length of the prefix that's guaranteed to already match where we are. It's like saying 'those first few letters of the pattern definitely line up here, so resume comparing from there.' The text pointer only ever moves forward, so each text character is looked at a constant number of times.
▸Why is KMP O(n+m) instead of O(n·m)?
Building the LPS table walks the pattern once: O(m). The search walks the text with i only ever moving forward (n steps) while j only jumps backward via the table — and the total backward jumps can't exceed the forward steps. So the search is O(n), and the whole thing is O(n+m). The naive method's nested re-checking is O(n·m), which blows up when the text and pattern are long and share lots of repeated letters.
How the work grows
O(n + m) is fair — grows in step with the data. Building the LPS table is one walk over the pattern: O(m). The text scan moves the text pointer i forward at most n times and never backward, and the pattern jumps via the table can't out-number those forward steps — so the scan is O(n). Together that's O(n+m), beating the naive O(n·m) that re-compares characters after every mismatch. The only extra memory is the LPS table, one number per pattern character: O(m).
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.