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.
What this is
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.
Never re-examining a character
The naive way to find a pattern in a text compares the pattern at every position, and on a mismatch slides forward by one and starts over. That re-reads characters it has already seen, and in the worst case — a text of "aaaaaaab" searched for "aaab" — it is O(n×m).
KMP eliminates the re-reading. When a mismatch occurs after matching k characters, those k characters are already known, so the algorithm can compute how far to slide without looking back at the text.
The result is O(n + m), with the text pointer never moving backwards. That property matters beyond the complexity: it means KMP can search a stream.
The failure function
The precomputation is the whole algorithm. For each prefix of the pattern, record the length of the longest proper prefix that is also a suffix of it.
For the pattern "ABABC":
Prefix
Longest prefix that is also a suffix
Value
A
—
0
AB
—
0
ABA
A
1
ABAB
AB
2
ABABC
—
0
So the table is [0, 0, 1, 2, 0].
What it means operationally: if a mismatch happens after matching "ABAB", the table says 2 — the first two characters "AB" of the pattern already match the text at the right place, so the pattern can be slid forward by 2 rather than 1, and comparison resumes at pattern index 2.
def build_table(pattern):
table = [0] * len(pattern)
k = 0
for i in range(1, len(pattern)):
while k and pattern[i] != pattern[k]:
k = table[k - 1] # fall back
if pattern[i] == pattern[k]:
k += 1
table[i] = k
return table
That function is itself a self-match of the pattern against itself, which is why it looks like the search loop.
The search
def kmp_search(text, pattern):
if not pattern:
return 0
table = build_table(pattern)
k = 0 # characters matched so far
for i, ch in enumerate(text):
while k and ch != pattern[k]:
k = table[k - 1] # slide, without moving i
if ch == pattern[k]:
k += 1
if k == len(pattern):
return i - k + 1 # match start index
return -1
The crucial observation is that i only ever increases. The inner while reduces k, never i — so each text character is examined a bounded number of times overall, giving O(n).
Algorithm
Preprocessing
Search
Worst case
Naive
None
O(n×m)
O(n×m)
KMP
O(m)
O(n)
O(n+m)
Boyer-Moore
O(m + alphabet)
O(n/m) best
O(n×m) worst, O(n) with refinements
Rabin-Karp
O(m)
O(n) expected
O(n×m) with bad hashing
The table, and the pointer that never goes back
KMP is usually presented as the LPS table plus a matching loop, and the table looks arbitrary until you see what the naive algorithm wastes. Count the character comparisons both ways on a text designed to be bad for the naive version, then read what each table entry means.
example_01.pyPython
def naive(text, pat):
comps, hits = 0, []
for i in range(len(text) - len(pat) + 1):
j = 0
while j < len(pat):
comps += 1
if text[i + j] != pat[j]:
break
j += 1
if j == len(pat):
hits.append(i)
return hits, comps
def build_lps(pat):
lps = [0] * len(pat)
length, i = 0, 1
while i < len(pat):
if pat[i] == pat[length]:
length += 1
lps[i] = length
i += 1
elif length:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
def kmp(text, pat):
lps = build_lps(pat)
comps, hits = 0, []
i = j = 0
while i < len(text):
comps += 1
if text[i] == pat[j]:
i += 1
j += 1
if j == len(pat):
hits.append(i - j)
j = lps[j - 1]
elif j:
j = lps[j - 1] # fall back in the PATTERN only
else:
i += 1
return hits, comps
text = "AAAAAAAAAAAAAAAAAAAB" * 20
pat = "AAAAAB"
n_hits, n_comps = naive(text, pat)
k_hits, k_comps = kmp(text, pat)
print("text: 'AAAA...AAAB' repeated, %d characters" % len(text))
print("pattern: %r" % pat)
print(" naive: %d matches, %d comparisons" % (len(n_hits), n_comps))
print(" KMP: %d matches, %d comparisons" % (len(k_hits), k_comps))
print(" same matches:", n_hits == k_hits)
# The naive version re-reads the same run of As for every starting
# position. KMP reads each character of the text once and never moves i
# backwards -- when a mismatch happens it slides the PATTERN instead.
#
# What the table stores: for each prefix of the pattern, the length of the
# longest proper prefix that is also a suffix of it. That is the amount
# already matched that can be reused after a mismatch.
for p in ("AAAAAB", "ABABACA", "ABCDE", "AABAACAABAA"):
lps = build_lps(p)
print()
print(" pattern %-12s %s" % (p, " ".join(p)))
print(" lps %-12s %s" % ("", " ".join(str(x) for x in lps)))
# Read 'ABABACA'. At index 3 the value is 2, because "ABAB" ends with
# "AB", which is also how it starts -- so after failing at index 4 we can
# resume as if two characters already matched, without re-reading them.
#
# 'ABCDE' is all zeros: nothing repeats, so a mismatch always restarts the
# pattern from the beginning. On that kind of pattern KMP does the same
# work as the naive version, and the table has bought nothing.
print()
print("%-14s %10s %10s" % ("pattern", "naive", "KMP"))
for p in ("AAAAAB", "ABCDE"):
_, nc = naive(text, p)
_, kc = kmp(text, p)
print("%-14s %10d %10d" % (p, nc, kc))
# So the guarantee is the point rather than the average: KMP is O(n + m)
# on EVERY input, where naive is O(n*m) on the bad ones. If your patterns
# and texts have little internal repetition, the naive scan is competitive
# and much simpler -- which is why real implementations often use it, with
# a fallback for the pathological cases.
Output
Things to try
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.
What to remember
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.
Boyer-Moore, and why it is usually faster in practice
KMP guarantees O(n+m) and examines every text character at least once. Boyer-Moore can skip characters entirely, and in practice it is faster on natural text.
It compares the pattern from right to left, and on a mismatch uses two heuristics:
Bad character rule. If the mismatched text character does not appear in the pattern at all, the whole pattern can be slid past it — a jump of m positions.
Good suffix rule. If a suffix of the pattern matched, slide to align the next occurrence of that suffix.
For long patterns and large alphabets, the average behaviour is sublinear — roughly O(n/m) — because most positions are skipped without examination. That is why grep, text editors and most standard library find implementations use Boyer-Moore or a hybrid.
The trade: Boyer-Moore needs random access to the text, so it cannot search a stream. KMP can. And KMP's guarantee is unconditional, where Boyer-Moore's worst case needs the Galil rule to be bounded.
KMP
Boyer-Moore
Direction
Left to right
Right to left
Skips characters
No
Yes
Practical speed on text
Good
Better
Streaming
Yes
No
Guarantee
O(n+m) always
Needs refinement for worst case
Rabin-Karp, and multi-pattern search
Rabin-Karp hashes the pattern and each window of the text, comparing hashes rather than characters. A rolling hash updates in O(1) as the window slides — remove the leaving character's contribution, add the entering one.
Its distinctive strength is searching for many patterns at once: hash all of them into a set and check each window's hash against it. That is O(n) regardless of how many patterns there are, which neither KMP nor Boyer-Moore can match.
It is also the basis of plagiarism detection and duplicate-file finding, where the hashes of many document fragments are compared.
The caveat is hash collisions: a matching hash must be verified by an actual comparison, and adversarial input can force collisions on every window, degrading to O(n×m).
Aho-Corasick is the other multi-pattern algorithm: a trie of all patterns with failure links generalising KMP's table. It finds every occurrence of every pattern in one linear pass, and it is what grep -F with many patterns and most intrusion-detection systems use.
Where these appear
Text editors and grep — substring search, usually Boyer-Moore or a hybrid.
Streaming search — log monitoring and network inspection, where KMP's forward-only property is required.
Bioinformatics — DNA sequence matching, where alphabets are small and patterns long.
Intrusion detection — Aho-Corasick matching thousands of signatures against a packet stream.
Plagiarism and duplicate detection — Rabin-Karp fingerprinting.
str.find and in in Python, which uses a hybrid of Boyer-Moore-Horspool and other techniques.
The practical point for everyday work: use the standard library. Python's in and str.find are implemented in C with a well-tuned hybrid, and they will beat a hand-written KMP by a wide margin. These algorithms matter for understanding why string search is fast, and for the cases the library does not cover — streaming, multi-pattern, or approximate matching.
Questions people ask
Why is it called the failure function? Because it says where to resume when a comparison fails.
Does KMP ever move backwards in the text? No — that is its defining property, and it is what makes streaming search possible.
Is KMP the fastest string search? No. Boyer-Moore is usually faster on natural text because it skips characters. KMP's advantage is the unconditional guarantee and streaming.
What does Python use for in? A hybrid based on Boyer-Moore-Horspool with additional heuristics, implemented in C.
How do I search for many patterns? Aho-Corasick, or Rabin-Karp with a hash set. Running KMP once per pattern is O(k(n+m)).
What about approximate matching? Different problem — edit distance dynamic programming, or specialised algorithms such as bitap.
Recap in one screen
Precompute, for each prefix, the longest proper prefix that is also a suffix — the failure table.
On a mismatch, that table says how far to slide without re-reading any text character.
The text pointer never moves backwards, giving O(n+m) and the ability to search a stream.
Boyer-Moore skips characters and is usually faster on real text, at the cost of needing random access.
Rabin-Karp and Aho-Corasick handle many patterns at once, which single-pattern algorithms cannot.
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
# Knuth-Morris-Pratt: never re-examine a character of the text.
def build_lps(pattern):
"""lps[i] = length of the longest proper prefix of pattern[:i+1]
that is also a suffix of it."""
lps = [0] * len(pattern)
length = 0
i = 1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
elif length:
length = lps[length - 1] # fall back, do NOT restart at 0
else:
lps[i] = 0
i += 1
return lps
pattern = "ababaca"
lps = build_lps(pattern)
print("pattern:", " ".join(pattern))
print("lps :", " ".join(str(x) for x in lps))
print("lps[4]=3 because 'ababa' starts and ends with 'aba'.")
def kmp_search(text, pattern):
lps = build_lps(pattern)
hits, comparisons = [], 0
i = j = 0 # i walks the text, j the pattern
while i < len(text):
comparisons += 1
if text[i] == pattern[j]:
i += 1
j += 1
if j == len(pattern):
hits.append(i - j)
j = lps[j - 1] # keep going for overlapping matches
elif j:
j = lps[j - 1] # slide the pattern, i never moves back
else:
i += 1
return hits, comparisons
def naive_search(text, pattern):
hits, comparisons = [], 0
for i in range(len(text) - len(pattern) + 1):
for j in range(len(pattern)):
comparisons += 1
if text[i + j] != pattern[j]:
break
else:
hits.append(i)
return hits, comparisons
text = "abababacabababacaba"
print()
print("text :", text)
print("KMP :", kmp_search(text, pattern))
print("naive :", naive_search(text, pattern))
# The input designed to make naive matching look bad.
print()
bad_text = "a" * 300 + "b"
bad_pattern = "a" * 20 + "b"
for name, fn in [("naive", naive_search), ("KMP", kmp_search)]:
hits, comparisons = fn(bad_text, bad_pattern)
print(f" {name:>5}: {comparisons:>6} comparisons, hits at {hits}")
Output
How the code works
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.
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.
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.
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.
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.
Check yourself
0 of 3
Answer without scrolling back up.
What does lps[i] store?
That overlap is the only information needed to know how far the pattern may safely slide after a mismatch.
In the search loop, what never happens?
The text index only moves forward, which is the O(n + m) guarantee. Naive matching restarts at i - j + 1 and re-reads characters.
After a full match, the code sets j = lps[j - 1] rather than 0. Why?
Set it to 0 and searching "aa" in "aaaa" reports fewer matches than there are.
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.
Fast Pattern Matching in StringsKnuth, Morris & Pratt, SIAM Journal on Computing 1977
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.