What you'll learn
Quick Answer
KMP (Knuth-Morris-Pratt) finds every occurrence of a pattern in a text in O(n + m) time by never re-checking a text character it has already matched. It precomputes a failure function, also called the LPS array, that tells it exactly how far to shift the pattern after a mismatch instead of restarting from the beginning. Brute-force search can degrade to O(n·m) on repetitive text; KMP never does, because it reuses information from previous comparisons.
The Problem With Brute-Force Search
The obvious way to find a pattern inside a text is to try every starting position: line up the pattern against the text, compare character by character, and if anything mismatches, slide the pattern one position to the right and start over from the pattern's first character.
That works, but it throws away information. Say you are searching for AABAA in AABAACAABAA and you have already matched AABA before hitting a mismatch. Brute force forgets all of that and restarts the comparison from scratch at the next position, even though the characters it just matched tell you something useful about what comes next.
On adversarial or repetitive input, text made of the same few characters like AAAAAAAAAA, this repeated restarting makes brute force run in O(n·m) time, where n is the text length and m is the pattern length. For a genome-sized text or a scanner checking many patterns, that is a real cost, not a theoretical one.
The Failure Function (LPS Array)
KMP's fix is to precompute, once per pattern, how much of the pattern's own text repeats itself. This precomputed array is called the failure function or the LPS array, short for "longest proper prefix that is also a suffix," and lps[i] stores the length of the longest prefix of the pattern that is also a suffix of the substring ending at index i.
For the pattern AABAA, running the actual computation gives:
pattern: A A B A A
index: 0 1 2 3 4
lps: 0 1 0 1 2lps[4] = 2 because the prefix AA, the first two characters, is also the suffix ending at index 4, the last two characters. That single number is what lets KMP skip re-checking those two characters after a mismatch later in the pattern.
Building this array takes O(m) time using two pointers, and it only needs to happen once, regardless of how long the text is.
Worked Example: Searching AABAA in AABAACAABAA
Running an actual KMP search for pattern AABAA against text AABAACAABAA (11 characters) finds matches starting at index 0 and index 6, confirmed against a brute-force scan of the same text, which returns the identical result.
Trace the interesting part: text index 5 is C, which mismatches against pattern index 4 (A) after the first four characters (AABA) already matched. Brute force would restart the whole comparison at text index 1. KMP instead checks lps[3] = 1, meaning it can resume the pattern comparison at pattern index 1 rather than index 0, because it already knows the single character A at the start of the pattern matches what it just saw.
The text pointer never moves backward. Only the pattern pointer jumps, using the LPS array, which is exactly why KMP never re-reads a text character it has already consumed. The same implementation was also run against highly repetitive text like AAAAAAAAAA and against text with no match at all, and every result matched a brute-force scan of the same inputs exactly.
Using the LPS Array to Search
The search loop keeps two pointers: one into the text (i) and one into the pattern (j). On a match, both advance. On a mismatch with j > 0, instead of resetting j to 0, it jumps to lps[j - 1] and retries the comparison at the same text position. Only when j is already 0 does the text pointer advance past a mismatch.
i = 0, j = 0
while i < text.length:
if text[i] == pattern[j]:
i++; j++
if j == pattern.length:
report match at i - j
j = lps[j - 1]
elif j != 0:
j = lps[j - 1]
else:
i++Because i only ever increases, the text is scanned once, start to finish, regardless of how many partial matches and mismatches occur along the way. That single guarantee is what produces the O(n + m) bound, and it is the detail that makes KMP correct rather than just fast: the pattern pointer's jump using lps never skips over a position where a match could actually have started.
Complexity, and When It Actually Matters
KMP runs in O(n + m) time, O(m) to build the LPS array and O(n) to scan the text, against brute force's worst case of O(n·m). For short, non-repetitive strings, the two perform similarly in practice, since brute force's worst case rarely triggers.
KMP earns its complexity when the pattern has internal repetition (DNA sequences, log-format matching, repeated tokens) or when the text is large enough that even a rare worst-case slowdown is unacceptable; search engines, intrusion detection, and bioinformatics pipelines all use it or a relative of it for this reason.
It is also a common interview topic, less for the implementation itself than for the LPS array concept: interviewers use it to check whether you can reason about reusing previously computed information instead of restarting work from zero, which is a habit of thought that carries over well beyond string matching.