Coding · Algorithms
KMP string search explained: how it works, code and complexity
Short answer
The Knuth-Morris-Pratt (KMP) algorithm finds every occurrence of a pattern of length m in a text of length n in O(n + m) time. It first builds a prefix function (also called the failure table) for the pattern: for each position, the length of the longest proper prefix that is also a suffix. When a mismatch happens, KMP uses this table to shift the pattern without ever moving backward in the text.
Open Regex testerWhat problem KMP solves
String search asks where a short pattern occurs in a longer text. The naive method tries every start position and compares characters one by one. On ordinary text it is fast, but on repetitive inputs it is slow: searching for aaaab in aaaaaaaaaa compares almost the whole pattern at each position, which gives O(n × m) time.
KMP never re-reads a text character after a mismatch. Donald Knuth, James H. Morris and Vaughan Pratt published it in 1977 in "Fast Pattern Matching in Strings".
The idea in plain words
Suppose you are searching for the pattern ABABC, you have matched ABAB, and the next text character is not C. The part you just matched, ABAB, ends with AB, which is also how the pattern begins. So you already know the next attempt starts with 2 matched characters, and you can continue comparing from pattern position 2 instead of starting over.
The prefix function stores these numbers. pi[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix of it (proper means not the whole string).
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| pattern[i] | A | B | A | B | A | C | A |
| pi[i] | 0 | 0 | 1 | 2 | 3 | 0 | 1 |
For example, pi[4] = 3 because ABABA begins and ends with ABA. pi[5] = 0 because no prefix of ABABAC ends with C.
Worked example, step by step
Search for the pattern ABABC (prefix function 0, 0, 1, 2, 0) in the text ABABABC. The variable k counts how many pattern characters are currently matched.
| Text position | Text char | k before | Action | k after |
|---|---|---|---|---|
| 0–3 | A B A B | 0 | Four matches in a row | 4 |
| 4 | A | 4 | Mismatch with pattern[4] = C: set k = pi[3] = 2, then A matches pattern[2] | 3 |
| 5 | B | 3 | Matches pattern[3] | 4 |
| 6 | C | 4 | Matches pattern[4]: full match ending at 6, so it starts at 6 − 5 + 1 = 2 | 5 → pi[4] = 0 |
The text pointer moved forward 7 times and never went back. The naive method would restart at position 1 and compare some characters again.
Python implementation
def prefix_function(p):
pi = [0] * len(p)
k = 0
for i in range(1, len(p)):
while k > 0 and p[i] != p[k]:
k = pi[k - 1] # fall back to a shorter border
if p[i] == p[k]:
k += 1
pi[i] = k
return pi
def kmp_search(text, pattern):
"""Return the start index of every occurrence (overlaps included)."""
if not pattern:
return []
pi, k, hits = prefix_function(pattern), 0, []
for i, ch in enumerate(text):
while k > 0 and ch != pattern[k]:
k = pi[k - 1]
if ch == pattern[k]:
k += 1
if k == len(pattern):
hits.append(i - k + 1)
k = pi[k - 1] # keep going to find overlapping matches
return hits
print(prefix_function("ABABACA")) # [0, 0, 1, 2, 3, 0, 1]
print(kmp_search("ABABABC", "ABABC")) # [2]
print(kmp_search("AAAAA", "AA")) # [0, 1, 2, 3]Time and space complexity
| Phase | Time | Space | Reason |
|---|---|---|---|
| Build prefix function | O(m) | O(m) | k increases at most once per step and each fallback decreases it, so total fallbacks are at most m. |
| Search | O(n) | O(1) extra | Same argument over the text: at most n increases, so at most n fallbacks. |
| Total | O(n + m) | O(m) | Worst case equals best case up to a constant; there is no bad input. |
The naive algorithm is O(n × m) in the worst case but often close to O(n) on natural-language text, so KMP's advantage shows mainly on repetitive data.
Variants and common mistakes
- Off-by-one in fallback: after a mismatch, set
k = pi[k - 1], notpi[k].piis indexed by the last matched position. - Using
ifinstead ofwhilefor the fallback: you may need several fallbacks in a row before a character matches. - Forgetting to reset k after a full match: set
k = pi[k - 1]to find overlapping matches, ork = 0for non-overlapping ones. - Concatenation trick: compute the prefix function of
pattern + separator + text, using a separator that appears in neither; every position where the value equals m is a match end. - The Z-algorithm computes a closely related array and also searches in O(n + m).
When to use it and real-world uses
| Algorithm | Best use |
|---|---|
| KMP | Guaranteed linear time for one pattern; streaming text, since it never looks back. |
| Boyer-Moore and variants | Long patterns over large alphabets; often skips many characters, used in tools such as grep. |
| Rabin-Karp | Many patterns of the same length, or plagiarism detection with rolling hashes. |
| Aho-Corasick | Many patterns at once; it generalizes KMP's failure links to a trie. |
| Suffix array or suffix automaton | Many different queries on the same fixed text. |
- Interview problems: implement
strStr(), shortest palindrome (prefix function ofs + "#" + reversed(s)), repeated substring pattern, smallest period of a string (m - pi[m - 1]). - Real world: searching in DNA sequences and network packet streams, where linear worst-case time matters.
FAQ
What is the prefix function or failure table in KMP?
For each position i of the pattern, it stores the length of the longest proper prefix of pattern[0..i] that is also a suffix of it. On a mismatch, KMP uses it to know how many characters are still matched.
What is the time complexity of KMP?
O(n + m): O(m) to build the prefix function and O(n) to scan the text. It is linear even in the worst case.
Is KMP faster than Python's str.find?
No. str.find is implemented in C with an optimized search algorithm and is much faster in practice. KMP is valuable for its guaranteed linear time, for learning, and for non-string sequences.
Does KMP find overlapping matches?
Yes, if after a full match you set k = pi[k - 1] instead of 0. For example, it finds AA at positions 0, 1, 2 and 3 in AAAAA.