StringsAlgorithmaka KMP, failure function, prefix function, LPS array

Knuth–Morris–Pratt (KMP)

Linear-time pattern matching that never re-reads text characters, using a precomputed failure (LPS) table of the pattern.

▶ VisualizePattern: Sliding WindowPractice (2)
Progress

Overview

KMP finds all occurrences of a pattern p in a text t in O(n + m) time. The idea is that when a comparison fails after matching j characters, those j characters are already known — they are p[0..j-1] — so the pattern can be shifted by an amount computed purely from the pattern itself, without re-examining the text.

The precomputation is the failure function, usually stored as an array lps (longest proper prefix which is also a suffix). lps[i] is the length of the longest border of p[0..i]: a string that is both a proper prefix and a proper suffix. Borders are the key to safe shifting.

pattern matchingO(n + m)failure functionprefix functionborders

Intuition

A mental model before the formal terms.

Suppose you have matched "aabaa" and the next text character breaks the match. A naive matcher slides one step and starts over. But look at "aabaa": its last two characters "aa" are also its first two. So if you slide the pattern so that its first "aa" sits where the last "aa" was, the first two characters are guaranteed to match already — you can continue comparing from p[2] instead of p[0]. The LPS array records, for every possible match length, exactly how much of the match survives the slide.

Worked example, p = "aabaaab": lps = [0, 1, 0, 1, 2, 2, 3]. lps[1] = 1 because "aa" has border "a". lps[2] = 0 because "aab" has none. lps[4] = 2 because "aabaa" has border "aa". At i = 5 ("aabaaa") the candidate is to extend the previous border of length 2 with p[2] = 'b', but p[5] = 'a' ≠ 'b', so we fall back to lps[1] = 1 and try p[1] = 'a': it matches, giving lps[5] = 2 (border "aa"). At i = 6, p[2] = 'b' equals p[6] = 'b', so lps[6] = 3 (border "aab").

How it works

  1. Build lps for the pattern. Keep len = length of the current border of p[0..i-1]. To extend to p[0..i]: if p[i] == p[len], set lps[i] = len + 1. Otherwise, if len > 0, fall back to len = lps[len - 1] and retry (the next-shorter border); if len == 0, set lps[i] = 0.
  2. Search: keep j = number of pattern characters matched so far. For each text character t[i]: while j > 0 and t[i] != p[j], set j = lps[j - 1]. Then if t[i] == p[j], increment j.
  3. When j == m, report a match starting at i - m + 1 and set j = lps[m - 1] so overlapping matches are still found.
  4. The text index i only ever moves forward; the fallback loop shrinks j, which was increased at most once per text character, so the total work is O(n).

Why it works

If p[0..j-1] matched the text ending at position i - 1 and p[j] mismatches, then any occurrence starting between the old start and i must align a prefix of p with a suffix of the already-matched p[0..j-1] — i.e. with a border. The longest such border is lps[j-1], and any shorter border is reached by iterating lps further. Skipping directly to the longest border never skips a real match.

The lps computation is correct because the borders of p[0..i] are exactly the borders of p[0..i-1] extended by one character when p[i] matches, and every border of p[0..i-1] is either the longest one or a border of that longest one, so the chain len → lps[len-1] → … enumerates all candidates in decreasing length.

Amortised analysis: j (or len) increases by at most 1 per iteration and never goes below 0, so the total number of decreases across the whole run is bounded by the number of increases, giving O(n + m) overall.

Recognition

How to tell a problem wants this.

  • The problem mentions prefix that is also a suffix, borders, periods of a string, or "shortest palindrome by prepending".
  • Pattern matching with guaranteed linear time, or inputs that are highly repetitive (DNA, binary).
  • Finding the smallest repeating unit: n - lps[n-1] is the period if it divides n.
“contiguous subarray” → Sliding Window

Interactive visualization

Play, step, change the input. ← → and space work too.

a
a
0
b
1
c
2
a
3
b
4
y
5
lps
0
0
1
2
3
4
5
1/27Phase 1: build the LPS table for the pattern. lps[i] = length of the longest proper prefix of pattern[0..i] that is also its suffix. It tells us how far to fall back on a mismatch.
Characters being comparedPrefix that is reused after a fallbackMatchMismatch
PseudocodeLearn Knuth–Morris–Pratt (KMP) →
1lps = [0]*m; len = 0
2for i in 1 .. m-1:
3  while len > 0 and pattern[i] != pattern[len]: len = lps[len-1]
4  if pattern[i] == pattern[len]: len += 1
5  lps[i] = len
6i = j = 0
7while i < n:
8  if text[i] == pattern[j]: i += 1; j += 1
9    if j == m: report match at i-m; j = lps[j-1]
10  else if j > 0: j = lps[j-1]   # fall back, keep i
11  else: i += 1
Variables
len0
m6
Complexity
best O(n + m)
avg O(n + m)
worst O(n + m)
space O(m)
Speed

Pseudocode

1lps[0] = 0, len = 0
2for i in 1 .. m-1:
3  while len > 0 and p[i] != p[len]: len = lps[len-1]
4  if p[i] == p[len]: len += 1
5  lps[i] = len
6j = 0
7for i in 0 .. n-1:
8  while j > 0 and t[i] != p[j]: j = lps[j-1]
9  if t[i] == p[j]: j += 1
10  if j == m: report i - m + 1; j = lps[m-1]

Implementations

11 · Build the LPS (failure) table
2def build_lps(p: str) -> list[int]:
3    m = len(p)
4    lps = [0] * m
5    length = 0  # length of the current border of p[0..i-1]
6    for i in range(1, m):
72 · Fall back to shorter borders on mismatch
8        while length > 0 and p[i] != p[length]:
9            length = lps[length - 1]
10        if p[i] == p[length]:
11            length += 1
12        lps[i] = length
13    return lps
14 
15 
16def kmp_search(text: str, pattern: str) -> list[int]:
173 · Scan the text with the automaton
18    n, m = len(text), len(pattern)
19    if m == 0:
20        return list(range(n + 1))
21    lps = build_lps(pattern)
22    matches: list[int] = []
23    j = 0  # characters of pattern matched so far
24    for i, ch in enumerate(text):
25        while j > 0 and ch != pattern[j]:
26            j = lps[j - 1]
27        if ch == pattern[j]:
28            j += 1
294 · Report a match and keep going for overlaps
30        if j == m:
31            matches.append(i - m + 1)
32            j = lps[m - 1]
33    return matches
Walkthrough
  1. lps = [0] * m builds the failure table; lps[0] is always 0 because a one-character prefix has no proper border.
  2. The variable is named length rather than len to avoid shadowing the built-in len().
  3. for i, ch in enumerate(text) yields the index and character together, so text[i] is not re-indexed in the fallback loop.
  4. The while j > 0 and ch != pattern[j] loop follows the border chain; j shrinks but i never moves back.
  5. j = lps[m - 1] after each report keeps overlapping matches.
Complexity (this implementation)
time O(n + m) · space O(m) for the LPS table

Pure-Python loops are slow; for a one-off search str.find (C implementation) wins. KMP in Python is worth it for the LPS table itself.

Language notes
  • Python strings are immutable and compare single characters as small string objects; the interpreter caches one-character Latin-1 strings, so p[i] != p[length] does not allocate.
  • enumerate is the idiomatic way to walk index and value; avoid range(len(text)) plus text[i] when both are needed.
  • Typing list[int] (PEP 585, Python 3.9+) needs no import from typing.
Common mistakes in this language
  • Naming the border length len and then calling len(p) later in the same scope — TypeError: int is not callable.
  • Using if in place of while for the fallback.
  • Resetting j = 0 after a match instead of j = lps[m - 1].
Language differences that matter here
  • Character comparison: C++ compares char bytes, JS/TS compare UTF-16 code units (charCodeAt), Python compares Unicode code points — results agree for ASCII, differ for non-BMP characters.
  • Python and JS/TS strings are immutable; C++ std::string is mutable but KMP never needs to modify either input.
  • Only the pattern must be in memory: in all four languages the text loop can be fed from a stream one character at a time.
  • The failure table is a small-integer array: std::vector<int> in C++, packed SMI array in JS/TS, list of int in Python.

Complexity

Best
O(n + m)
Average
O(n + m)
Worst
O(n + m)
Space
O(m)

Text is read strictly left to right, once — KMP works on streams.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Guaranteed linear-time single-pattern search, especially on repetitive input.
  • Streaming text where you cannot back up (only the pattern is preprocessed).
  • Any question about borders or periods of a string: shortest repeating unit, shortest palindrome by prepending, longest prefix-suffix.
Avoid it when
  • Searching many patterns at once — build Aho–Corasick instead.
  • Many queries on one fixed text — Suffix Array preprocesses the text once.
  • Short patterns on natural-language text, where Naive String Matching is simpler and about as fast.

Alternatives

Z-AlgorithmRabin–KarpNaive String MatchingAho–Corasick
Compare: KMP vs Rabin-Karp

Common mistakes

  • Computing lps[i] as "longest prefix that equals a suffix" without the proper restriction — the whole string is trivially both, so lps[i] would be i + 1.
  • Using if instead of while for the fallback len = lps[len - 1] — one fallback is not always enough (see the i = 5 step in "aabaaab").
  • After a full match, resetting j = 0 instead of j = lps[m - 1], which misses overlapping occurrences.
  • Off-by-one in the reported start index: it is i - m + 1, not i - m.

Interview patterns

  • Implement strStr in linear time.
  • Shortest palindrome: build lps of s + "#" + reverse(s) to find the longest palindromic prefix.
  • Repeated substring pattern: s is periodic iff n % (n - lps[n-1]) == 0 and lps[n-1] > 0.
  • Count occurrences of each prefix of s in s using the prefix function.
Interview questions on this
Mock interviews

Example problems

Repeated DNA SequencesmediumFind the Index of the First Occurrenceeasy