KMP pattern matching
hardThe failure function records, for each prefix, the longest proper prefix that is also a suffix - so a mismatch slides the pattern forward without re-reading a single character.
O(n + m)Space O(m)Saved in this browser - no sign-up, nothing sent anywhere.
How kmp pattern matching works
The naive matcher's waste is re-reading text it has already seen. KMP preprocesses the pattern into a failure function: lps[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix of it. For ababd that table is [0, 0, 1, 2, 0] - after matching abab, the last two characters ab are also the pattern's first two.
That table turns every mismatch into a jump. After j characters have matched, a mismatch sets j = lps[j - 1] - the pattern slides forward exactly as far as its own self-overlap allows - while the text pointer stays put. The text index only ever advances, and that single property caps the scan at n steps regardless of the pattern.
The build phase is the search phase run on the pattern against itself: the same fall-back through lps, one index chasing another. The result is deterministic O(n + m) matching - no hashing, no randomness, no false positives. Reach for it when one pattern is searched repeatedly, when the input streams past only once, or when the worst case must be guaranteed.
Step by step
- Build lps for ababd: b extends nothing, a and b grow the prefix to 1 then 2, d falls back to 0. Table: [0, 0, 1, 2, 0].
- Scan abababd. The first four characters match the pattern: after abab, the text pointer i is 4 and the pattern pointer j is 4.
- text[4] = a but pattern[4] = d. j falls back to lps[3] = 2 - the matched suffix ab is reused as a prefix - and i does not move.
- From there a, b, d all match: j reaches 5 = m, a full match reported at i - j = 2.
- After the hit, j falls back to lps[4] = 0 rather than restarting - that is how overlapping matches would be caught. Here the text simply ends.
- Total: 8 comparisons for a 7-character text, and i moved forward only. The naive matcher re-reads text[2] and text[3]; KMP never touched them twice.
Complexity
| Worst case time | O(n + m) |
|---|---|
| Space | O(m) |
The text index only ever advances, capping the scan at n steps.
Reference implementation
Python
def build_lps(p):
"""lps[i] = length of the longest proper prefix of p[:i+1]
that is also a suffix of it."""
lps = [0] * len(p)
length, i = 0, 1
while i < len(p):
if p[i] == p[length]:
length += 1
lps[i] = length
i += 1
elif length:
length = lps[length - 1] # fall back, do not restart
else:
lps[i] = 0
i += 1
return lps
def kmp(text, pattern):
lps = build_lps(pattern)
hits, i, j = [], 0, 0
while i < len(text):
if text[i] == pattern[j]:
i += 1
j += 1
if j == len(pattern):
hits.append(i - j)
j = lps[j - 1]
elif j:
j = lps[j - 1] # i never moves backwards
else:
i += 1
return hitsJavaScript
function buildLps(p) {
const lps = new Array(p.length).fill(0);
let len = 0, i = 1;
while (i < p.length) {
if (p[i] === p[len]) lps[i++] = ++len;
else if (len) len = lps[len - 1];
else lps[i++] = 0;
}
return lps;
}
function kmp(text, pattern) {
const lps = buildLps(pattern), hits = [];
let i = 0, j = 0;
while (i < text.length) {
if (text[i] === pattern[j]) {
i++; j++;
if (j === pattern.length) { hits.push(i - j); j = lps[j - 1]; }
} else if (j) j = lps[j - 1];
else i++;
}
return hits;
}Java
static int[] buildLps(String p) {
int[] lps = new int[p.length()];
int len = 0, i = 1;
while (i < p.length()) {
if (p.charAt(i) == p.charAt(len)) lps[i++] = ++len;
else if (len > 0) len = lps[len - 1];
else lps[i++] = 0;
}
return lps;
}Worth noticing
lps[i] is the longest proper prefix that is also a suffix
For 'ababd', lps = [0,0,1,2,0]. After matching 'abab' and failing, the last two characters 'ab' are also the pattern's first two - so the pattern can jump forward two places without re-reading anything.
`i` never moves backwards, and that is the whole guarantee
The text pointer only ever advances. On a mismatch it is `j` that falls back, using information already computed. That single property caps the scan at O(n) regardless of the pattern.
The failure function is built by KMP matching the pattern against itself
The preprocessing loop is the same fall-back logic, run on the pattern alone. Once you see that, the two halves of the algorithm stop looking like separate tricks.
O(n + m) with no hashing and no randomness
Deterministic, no false positives, no worst-case blowup. The cost is O(m) preprocessing and a failure array - cheap unless the pattern changes on every query.
Common pitfalls
- Falling back with len = 0 on a build mismatch instead of len = lps[len - 1]. It passes short tests, then writes wrong table entries once a pattern contains nested repeats.
- Mixing lps conventions. Here lps[i] covers pattern[0..i] inclusive with lps[0] = 0; the shifted convention (size m + 1, first entry -1) indexes differently, and blending them lands every fall-back one off.
- Resetting j to 0 after a full match. Using j = lps[m - 1] instead is what finds overlapping occurrences - abab appears twice in ababab, and the reset version misses one.
- Letting lps[i] count the whole prefix rather than a proper one. If a fall-back can return j unchanged, the search loop stops making progress and spins forever on repetitive patterns.
Where it is used
- Streaming search: the text pointer never rewinds, so KMP works on input you can read only once - network data, tape-style logs, pipes.
- Interview problems that are secretly the failure function: shortest palindrome, repeated substring pattern, and longest happy prefix all read straight off lps.
- Matching untrusted input where O(n·m) blowup is an attack surface - intrusion detection and protocol scanners need the deterministic bound.
- The canonical follow-up to implement strStr: first the naive loop, then KMP when the interviewer asks for guaranteed linear time.
Frequently asked questions
What is the time and space complexity of KMP?
O(n + m) worst case - O(m) to build the failure function plus O(n) for the scan - and O(m) extra space for the lps array. The bound holds because the text index only ever advances, capping the scan at n steps no matter how the pattern repeats.
What does the lps failure function actually store?
lps[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix of it - for ababd, [0, 0, 1, 2, 0]. On a mismatch after j matches, lps[j - 1] says how many of those characters still count, so nothing is re-read.
Does KMP find overlapping matches?
Yes. After a full match this implementation sets j = lps[m - 1] instead of 0, keeping the part of the match that is also a prefix. Searching abab in ababab reports hits at 0 and 2 in a single pass.
When should I use KMP instead of Rabin-Karp?
Use KMP when the worst case must be deterministic: no hash collisions, no false positives, no adversarial inputs to worry about. Rabin-Karp earns its keep when many patterns are searched at once, checking one rolled hash against a whole set - something KMP cannot do in one scan.