Back to Study Material Data Structures and Algorithms

KMP Algorithm

The Knuth-Morris-Pratt algorithm, commonly called KMP, is a string pattern matching algorithm that finds all occurrences of a pattern P of length m in a te...

KMP Algorithm

Linear-Time Pattern Matching Using the Failure Function

The Knuth-Morris-Pratt algorithm, commonly called KMP, is a string pattern matching algorithm that finds all occurrences of a pattern P of length m in a text T of length n in O(n plus m) time. It was independently discovered by Donald Knuth, James Morris, and Vaughan Pratt and published in 1977.

The core insight behind KMP is that when a mismatch occurs during matching, you should not discard all the comparison work done so far. When you are comparing T[i] with P[j] and they do not match, the characters T[i-j] through T[i-1] are already known because you matched P[0] through P[j-1] against them. This known portion might end with a prefix of P, which means you can skip ahead and resume comparison from a later position in P rather than restarting from P[0].

KMP precomputes a failure function, also called the prefix function or lps (longest proper prefix which is also a suffix) array, for the pattern P. The value lps[j] is the length of the longest proper prefix of P[0..j] that is also a suffix. For the pattern "ABABC", the lps array is [0, 0, 1, 2, 0]. When a mismatch occurs at pattern index j, you fall back to lps[j-1] instead of resetting j to zero, preserving as much matched information as possible.

Building the lps array takes O(m) time. The matching phase takes O(n) time because the pointer i into T never decreases, and the pointer j into P moves left only by the amount it previously moved right, so the total number of steps across both pointers is bounded by 2n.

A worked trace: text "AABAABAAA", pattern "AABAAA". Compute lps for "AABAAA" as [0, 1, 0, 1, 2, 1]. During matching, when a mismatch occurs at text position 5 and pattern position 3, instead of restarting at text position 3, you fall back to pattern position lps[2] equals 0 and continue from text position 5, saving three comparisons.

KMP is particularly effective when the pattern has repeating structure (a high lps value), such as "AAAAAB" in a text of all A's. The naive algorithm would be O(n times m) in this case; KMP remains O(n plus m).

Applications beyond direct text search: KMP's failure function is used in algorithms for finding the shortest period of a string, checking whether one string is a rotation of another, and counting occurrences of the pattern in a circular buffer.

Interview tip: to implement KMP correctly in an interview, first write the lps construction separately and verify it on a few examples before proceeding to the matching phase. Mixing the two in a single function without testing the lps step is the most common source of bugs.