After a partial match of length k that ends in a mismatch, brute force discards every comparison it just made. KMP precomputes, for every possible k, the longest prefix of the pattern that is also a suffix of pattern[0..k-1].

With that table, search resumes from the right place in the pattern without rescanning a single text character, and the worst case drops from O(n*m) to O(n+m).

Searching for the pattern ABCABD, suppose the first five characters ABCAB matched before a mismatch at D.

Brute force would shift the pattern by one position and restart. The suffix AB of the matched portion is also a prefix of the pattern, so KMP shifts the pattern forward until that prefix AB lines up with the matched suffix AB, then resumes comparing from position 2 in the pattern.

The text pointer never moves backward. It stays where the mismatch happened, and only the pattern pointer jumps to a smaller position. The precomputed information that drives the jump is called the failure function, or the prefix table.

The failure function is an array called lps (longest proper prefix which is also a suffix). For each index i in the pattern, lps[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix of pattern[0..i].

"Proper" prefix means the entire string itself does not count. For ABA, the proper prefixes are "", "A", "AB", and the suffixes are "", "A", "BA", "ABA". The longest proper prefix that is also a suffix is "A", length 1.

The lps array for pattern ABCABCABD:

At index 8, the prefix-suffix match of length 5 cannot be extended by D. The construction does not immediately set lps[8] = 0. It first falls back to lps[4] = 2, which says the next candidate length is 2 (prefix AB). The character after AB in the pattern is C, not D, so that fails too. Falling back again to lps[1] = 0 gives no shorter match. Only then does lps[8] become 0.

The construction uses the same border-fallback recurrence as the search.

Cyan nodes have no prefix-suffix match. Green nodes have a match, and dotted arrows show which prefix aligns with which suffix. The red node breaks the chain.

Building the Failure Function

Construction:

The search maintains two pointers: i for the text and j for the pattern. i only ever moves forward.

Rules:

Why the Shift Is Safe

Rule 3 needs justification. After matching j characters, the shift j → lps[j-1] skips a number of pattern positions; we need to know that no skipped alignment could have been a match.

Take the running example: pattern ABCABD, text contains ...ABCAB?... where ? is the mismatching character at position i. We matched j = 5 characters, so lps[4] = 2.

Smaller shifts (1 or 2) cannot succeed because they would require lps[4] to be longer than 2, which contradicts how lps was computed. Larger shifts could be safe but would skip past alignments that might match. The fallback to lps[j-1] is the largest safe shift, which is exactly what is needed.

The Strong (Refined) Failure Function

A small optimization: when pattern[lps[j-1]] == pattern[j], falling back to lps[j-1] is wasted because the same mismatching character will fail again at the new position. The "strong" failure function fixes this by setting the entry to lps[lps[j-1] - 1] instead in that case.

The improvement is a constant factor. The asymptotic complexity stays O(n + m), and most implementations use the basic version. The strong variant matters in competitive programming where constant factors are tight.

Full KMP search:

Text: ABCABCABCABD Pattern: ABCABD LPS array: [0, 0, 0, 1, 2, 0]

The lps array for ABCABD:

Now the search trace:

The text pointer i never moved backward. At steps 6 and 10, on mismatch, only j fell back from 5 to 2, reusing the fact that the AB at the end of the matched portion is also a prefix of the pattern.

Compare with brute force on the same input. Brute force would try starting positions 0 through 6, comparing up to 6 characters each, for up to 42 comparisons. KMP made 14 comparison steps, and the text pointer advanced monotonically from 0 to 12.

The inner logic has branches where i does not advance (the lps fallback), so linearity is not immediate. The argument is amortized using the pattern pointer j:

Total work in the search loop is at most 2n. Preprocessing uses the identical argument with the pattern length m, giving O(m). Combined: O(n + m).

Space: O(m) for the lps array.

The failure function appears in several problems that are not obviously substring search.

Repeated Substring Pattern

Problem: check whether a string s is built by repeating one of its substrings.

If lps[m-1] > 0 and m % (m - lps[m-1]) == 0, then s is the first m - lps[m-1] characters repeated.

Why: lps[m-1] is the longest proper prefix that equals a suffix. Let L = m - lps[m-1]. The prefix-suffix overlap means shifting the string by L positions still matches, which only happens when the string is periodic with period L.

Shortest Palindrome

Problem: find the shortest palindrome formed by prepending characters to s.

Find the longest palindromic prefix of s. Whatever remains after that prefix must be reversed and prepended. To find the longest palindromic prefix, build the lps array of s + "#" + reverse(s). The lps value at the last index is the length of the longest prefix of s that equals a suffix of reverse(s), which is the longest palindromic prefix.

The # separator matters. Without it, the suffix of reverse(s) could continue matching into the prefix of s, giving an lps value larger than len(s) and producing a wrong answer.

Longest Happy Prefix

Problem: find the longest substring of s that is both a prefix and a suffix (not the entire string).

That is exactly lps[m-1]. The answer is s[0..lps[m-1]-1].

String Rotation Check

Problem: check whether s2 is a rotation of s1.

If s2 is a rotation of s1, then s2 appears as a substring of s1 + s1. Run KMP for s2 in s1 + s1 in O(n), versus O(n^2) for brute force.

Compared to brute force O(n*m), KMP is a strict improvement when the pattern has repeated prefixes that cause many partial matches. On text "AAAAAB" with pattern "AAAB", KMP's advantage is largest.

Compared to Rabin-Karp, KMP has a guaranteed worst case with no hash collisions. The cost is O(m) extra space for the failure function.