When a match fails, naive search throws away everything it just learned and restarts. KMP precomputes how far it can safely skip — and never re-reads a character of the text.
Controls
textpattern
LPS table
Matching
step 0
Insight
The LPS array stores, for each prefix, the length of the longest proper prefix that is also a suffix. On a mismatch it tells you how much of the pattern is already re-matched.
comparisons0
text pointer0
backtracks0
matches found0
Complexity
KMPO(n+m)
Naive worst caseO(n·m)
SpaceO(m)
KMP String Matching
Never re-read a character you have already seen.
Quick Context
Knuth–Morris–Pratt finds a pattern inside a text in O(n + m), where naive search can take O(n·m). The insight: a partial match already tells you something, so there is no need to start over.
What Naive Search Wastes
Naive search compares the pattern at position 0. On a mismatch it shifts by one and restarts from the beginning of the pattern, re-reading text characters it has already examined.
Switch to naive mode and watch the backtrack counter climb. With a text like "aaaaaaab" and pattern "aaab" it re-reads almost everything, every time — that is the O(n·m) worst case.
The LPS Table
KMP precomputes an array over the pattern only. LPS[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix of it.
For ababd the table is [0,0,1,2,0]. At index 3 ("abab") the value 2 means "ab" is both a prefix and a suffix.
So if a mismatch happens after matching "abab", those last two characters are already a valid prefix — the pattern can slide forward and resume at index 2, without moving the text pointer at all.
The Text Pointer Never Goes Backwards
This is the guarantee that produces the linear bound. In KMP, i (the text index) only ever increases — watch the backtrack counter stay at zero. Only the pattern index moves back, and it can only decrease as many times as it increased.
Total work is therefore at most 2n for the search plus O(m) to build the table — hence O(n + m).
It also means KMP can run on a stream: you never need to store or rewind the text, which matters for network and file processing.
In Context
KMP is the classic, but not always the fastest in practice. Boyer–Moore scans the pattern right-to-left and can skip whole blocks, making it typically faster for long patterns — it is what most grep implementations use. Rabin–Karp uses rolling hashes and is well suited to searching for many patterns at once.
KMP's distinguishing strength is its worst-case guarantee and its ability to work on streaming input without buffering.
Interactive Exploration Guide
Look at the LPS table first. Non-zero entries mark places where a prefix reappears as a suffix — the only places a shortcut is possible.
Step through KMP and watch the pattern jump forward by several positions on a mismatch, instead of one.
Keep an eye on the text pointer. It never decreases, which is the entire source of the linear guarantee.
Switch to naive mode on the same input and watch the backtrack counter climb while KMP's stays at zero.
Try text 'aaaaaaaab' with pattern 'aaab'. This is naive search's worst case, and the comparison gap becomes dramatic.
Key Takeaway
KMP precomputes an LPS table describing the pattern's self-overlap, then uses it to shift intelligently after a mismatch. Because the text pointer never moves backwards, matching is O(n+m) with a worst-case guarantee — and it works on streams that can never be rewound.
Cheat sheet
KMP String Matching
When a match fails, naive search throws away everything it just learned and restarts. KMP precomputes how far it can safely skip — and never re-reads a character of the text.