vizlearn
Home / Algorithms

KMP String Matching

Algorithms & Data StructuresBy Updated

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

KMP O(n+m)
Naive worst case O(n·m)
Space O(m)

Overview

For each pattern position, store the length of the longest proper prefix that is also a suffix of the pattern prefix ending there. A proper prefix is shorter than the whole string.

Build the prefix table

For pattern ABABC, the table is [0, 0, 1, 2, 0]. The prefix ABAB ends in AB, which is also a prefix, so its entry is 2. This table is sometimes called the LPS or failure table.

Reuse a partial match

Suppose the search has matched ABAB but the next text character does not match C. The table says the final AB could still match the start of the pattern. KMP keeps that overlap and resumes at pattern index 2 instead of restarting from zero. The text index never moves backward.

Choose KMP search and follow a mismatch; then compare with Naive search (compare). The naive method restarts after each mismatch and can revisit many text positions. KMP builds the table in O(m) time and scans the text in O(n), for total O(n + m) time and O(m) extra space, where n is text length and m is pattern length.

Why the bound is linear

Each text character advances the text index once. The pattern index can fall back through table entries, but across the scan it cannot increase more times than the text index advances. The preprocessing and scan are therefore linear in their input lengths. KMP can process a stream because it does not need to rewind the text.

When to use it

KMP is useful when a worst-case linear bound matters or when text arrives as a stream. Boyer–Moore often skips more characters on natural-language text and can be faster in practice, but its performance depends on the pattern, alphabet, and implementation. Choose based on the data and required guarantees.

Common mistakes with KMP String Matching

  • Using the longest prefix instead of a proper prefix: an entry cannot equal the whole pattern prefix.
  • Resetting the pattern index to zero after every mismatch: that discards the overlap KMP was designed to keep.
  • Moving the text index backward: KMP’s linear scan depends on keeping it monotonic.
  • Confusing substring search with many-pattern search: KMP handles one pattern; Aho–Corasick is designed for many patterns.

Sources and next steps

Run it in Python

The prefix table built and printed for a pattern with real internal repetition, then the search, then a comparison count against the naive matcher on the input that makes naive matching look bad.

kmp.pyPython 3
Output
How the code works
  1. length = lps[length - 1]The line that makes the table build linear, and the one that looks wrong. On a mismatch the fallback is to the next-best border already computed — the table is built using itself.
  2. lps[i]For each prefix, how much of it is also a suffix of itself. That overlap is the only thing KMP needs in order to know how far it may safely slide after a mismatch.
  3. elif j: j = lps[j - 1]The search's whole trick. On a mismatch the pattern slides forward while i stays put, because the table already proves the skipped alignments cannot match.
  4. i never decreasesEvery character of the text is looked at a bounded number of times, which is the O(n + m) guarantee. Naive matching restarts at i - j + 1 and can re-read the same characters over and over.
  5. j = lps[j - 1] after a hitFalling back rather than resetting to 0 is what finds overlapping occurrences. Set it to 0 and searching for "aaa" in "aaaaa" reports one match instead of three.
Change one thing
  • Build the table for "aaaa" and for "abcd". One is all overlap, the other has none — the two extremes of what the table can say.
  • Lengthen bad_text to 3,000 a's. The naive count grows quadratically while the KMP count grows linearly.
  • Search for "aa" in "aaaa". Three overlapping hits — then set the post-hit line to j = 0 and watch one disappear.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: switch Show to Naive search (compare). Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. What does lps[i] store?
  2. In the search loop, what never happens?
  3. After a full match, the code sets j = lps[j - 1] rather than 0. Why?





 Cheat sheet
KMP String Matching
Build a failure function from the pattern and scan the text in O(n + m) total, never re-reading a character after a mismatch.
ALGORITHMS · vizlearn.in/dsa/kmp_string_matching.html
More in Algorithms
AlgorithmsBig-O Notation and Time ComplexityAlgorithmsPython List LabAlgorithmsPython String LabAlgorithmsPython Dictionary Lab
Further reading
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact