The Knuth-Morris-Pratt algorithm, often called KMP, is a string matching algorithm that finds all occurrences of a pattern inside a text without rechecking characters unnecessarily. This cheat sheet helps students remember the preprocessing step, the search step, and the role of the LPS array. It is especially useful when analyzing algorithm efficiency, implementing exact string search, or preparing for data structures and algorithms exams.
KMP works by using information about the pattern itself to decide how far the pattern can shift after a mismatch. The main preprocessing formula builds LPS[i], the length of the longest proper prefix of pattern[0..i] that is also a suffix of pattern[0..i]. During search, if text[i] and pattern[j] mismatch, KMP sets j = LPS[j - 1] instead of moving the text pointer backward.
This gives a total running time of O(n + m), where n is the text length and m is the pattern length.
Key Facts
- KMP searches for a pattern P of length m in a text T of length n in O(n + m) time.
- The LPS value LPS[i] is the length of the longest proper prefix of P[0..i] that is also a suffix of P[0..i].
- A proper prefix is a prefix that is not equal to the entire string.
- During search, if T[i] == P[j], advance both pointers with i = i + 1 and j = j + 1.
- When j == m, a full match is found starting at index i - m, then continue with j = LPS[j - 1].
- During a mismatch with j > 0, update j = LPS[j - 1] and do not increment i.
- During a mismatch with j == 0, update i = i + 1 because no prefix of the pattern can currently help.
- KMP never moves the text pointer i backward, which is the key reason its search phase is linear.
Vocabulary
- Pattern
- The string P that the algorithm tries to find inside a larger text.
- Text
- The string T being searched for occurrences of the pattern.
- LPS Array
- An array where LPS[i] stores the longest proper prefix length of P[0..i] that is also a suffix.
- Proper Prefix
- A prefix of a string that does not include the entire string itself.
- Mismatch
- A comparison where the current text character and pattern character are not equal.
- Time Complexity
- A measure of how the running time of an algorithm grows as the input size grows.
Common Mistakes to Avoid
- Confusing LPS with the length of any repeated substring is wrong because LPS only uses prefixes that are also suffixes of the current pattern prefix.
- Incrementing the text pointer i after every mismatch is wrong when j > 0 because KMP must first reuse the partial match by setting j = LPS[j - 1].
- Setting j = LPS[j] after a mismatch is wrong because the last matched pattern index is j - 1, so the correct fallback is LPS[j - 1].
- Forgetting to continue after finding a match is wrong because KMP can find overlapping matches by setting j = LPS[j - 1].
- Using O(nm) reasoning for KMP is wrong because the text pointer never moves backward and each fallback is controlled by the LPS array.
Practice Questions
- 1 Compute the LPS array for the pattern ABABAC.
- 2 Using KMP, find all starting indices of the pattern ABA in the text ABABABA.
- 3 For text length n = 1000 and pattern length m = 25, what is the asymptotic time complexity of KMP search including preprocessing?
- 4 Explain why KMP can skip comparisons after a mismatch without missing a valid match.
Understanding KMP String Matching Reference
The LPS table is best understood as a record of useful overlap. Suppose part of a pattern has matched, then the next character fails. Some characters at the end of the matched part may already be the beginning of another possible copy of the pattern.
KMP keeps that overlap instead of discarding it. For the pattern ABABAC, the LPS entries are zero, zero, one, two, three, zero.
At the fifth position, ABABA ends with ABA, which is the same as its first three characters. A mismatch after that point does not erase evidence that ABA has already matched.
Building the table uses two positions. One position moves from left to right through the pattern. The other stores the current candidate length for a prefix that might match a suffix.
When the next characters agree, the candidate length grows by one and becomes the LPS value for that position. When they disagree, the candidate does not always return directly to zero. It falls back to the earlier LPS value for the current candidate.
This repeated fallback is the subtle part of KMP. It tests shorter overlaps without restarting the scan of the pattern from its beginning.
A useful way to trace the search is to state what the pattern index means at every moment. If its value is four, the first four pattern characters match the text characters immediately before the current text position. After a mismatch, changing the pattern index preserves this statement.
The text character is then compared with the next possible pattern character. Students often make the mistake of advancing the text position during every mismatch. That skips a comparison that may begin an overlapping match.
Another common mistake is handling a completed match as if the pattern must restart at zero. Patterns can overlap, so the LPS value after a match matters.
KMP appears in tasks that search long sequences repeatedly. Examples include finding a short DNA sequence in genomic data, detecting a phrase in a document, scanning log files for an error marker, and locating a command in network data. In practice, many libraries offer built in search functions, but KMP remains important because it teaches a general algorithm idea.
Previous work can guide the next step. When studying it, trace small patterns with repeated pieces such as AABAACAABAA or ABABAB.
Write the table by hand, then trace both matching and mismatch cases. Pay close attention to index boundaries, especially the fallback from a pattern index of one and the update after a full match.