What is the KMP String Matching Algorithm?
Learn how the KMP algorithm uses the LPS array to find patterns in O(n+m) time, with code and interview tips.
Expected Interview Answer
The Knuth-Morris-Pratt (KMP) algorithm finds all occurrences of a pattern in a text in O(n + m) time by precomputing a failure function (also called the longest-prefix-suffix or LPS array) that lets the search skip re-comparing characters it has already matched, instead of the O(n*m) worst case of naive matching.
The core insight is that when a mismatch occurs after some characters have already matched, the pattern itself tells you how far you can safely shift without re-examining text you've already compared, because the matched prefix of the pattern overlaps with a suffix of what was just matched. The LPS array is built once per pattern in O(m) time: LPS[i] stores the length of the longest proper prefix of pattern[0..i] that is also a suffix of it. During the search phase, on a mismatch you don't backtrack the text pointer; you only move the pattern pointer to LPS[j-1], which guarantees each text character is examined a bounded number of times, giving the O(n+m) total. KMP is preferred over naive matching for large texts, DNA sequence search, and text editors' find features, though Boyer-Moore and Rabin-Karp offer different tradeoffs for other workloads.
- Guaranteed O(n + m) time, no quadratic worst case
- Never backtracks the text pointer
- LPS array precomputed once, reused across the whole search
- Deterministic, no hashing collisions to worry about
AI Mentor Explanation
KMP is like a bowling coach analyzing a batter's known scoring pattern against a full innings without rebowling deliveries the batter already faced. Before the match, the coach studies the target pattern itself and notes which partial sequences of shots repeat within it, building a cheat sheet of how far to jump ahead on a mismatch. When a delivery breaks the expected pattern, the coach doesn't restart from the very first ball faced; the cheat sheet says exactly how many balls of overlap can be reused. This is why KMP never re-examines a ball of the innings it has already accounted for, unlike naively restarting the pattern check from scratch at every position.
Step-by-Step Explanation
Step 1
Build the LPS array
For the pattern, compute for each index the length of the longest proper prefix that is also a suffix, in O(m) time.
Step 2
Initialize two pointers
i walks the text, j walks the pattern; both start at 0.
Step 3
Match or fall back on mismatch
On a match, advance both i and j; on a mismatch, set j = LPS[j-1] instead of resetting i.
Step 4
Record matches and continue
When j reaches the pattern length, record a match at i - j and continue with j = LPS[j-1] to find overlapping matches.
What Interviewer Expects
- Explain what the LPS/failure function represents (longest proper prefix that is also a suffix)
- State the O(n + m) time complexity and why the text pointer never backtracks
- Walk through a mismatch case showing the pattern pointer jumping via LPS, not resetting to zero
- Compare briefly with naive matching and mention alternatives like Rabin-Karp or Boyer-Moore
Common Mistakes
- Backtracking the text pointer on a mismatch, which reintroduces quadratic behavior
- Confusing the LPS array with simple prefix counts instead of prefix-that-is-also-suffix
- Forgetting to continue searching for overlapping matches after finding one
- Misstating the LPS construction complexity as anything other than O(m)
Best Answer (HR Friendly)
“KMP finds a pattern inside text fast by first studying the pattern itself to learn how to skip ahead smartly on a mismatch, instead of starting over from scratch each time. I'd reach for it whenever I need guaranteed linear-time substring search, like scanning huge log files or DNA sequences.”
Code Example
def build_lps(pattern):
lps = [0] * len(pattern)
length = 0
i = 1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
elif length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
def kmp_search(text, pattern):
if not pattern:
return []
lps = build_lps(pattern)
matches = []
i = j = 0
while i < len(text):
if text[i] == pattern[j]:
i += 1
j += 1
if j == len(pattern):
matches.append(i - j)
j = lps[j - 1]
elif j != 0:
j = lps[j - 1]
else:
i += 1
return matchesFollow-up Questions
- How would you modify KMP to find overlapping matches?
- How does KMP compare to Rabin-Karp for searching multiple patterns?
- What is the worst-case time complexity of building the LPS array?
- How would you use KMP to check if one string is a rotation of another?
MCQ Practice
1. What does LPS[i] represent in the KMP failure function?
LPS[i] stores how much of the pattern can be reused after a mismatch, based on prefix-suffix overlap.
2. What is the overall time complexity of KMP string matching?
Building the LPS array takes O(m) and the search phase takes O(n), giving O(n + m) total.
3. On a mismatch in the search phase, what does KMP do with the text pointer i?
KMP never backtracks the text pointer; only the pattern pointer j is adjusted using the LPS array.
Flash Cards
What does the KMP LPS array store? — For each prefix of the pattern, the length of its longest proper prefix that is also a suffix.
What is the time complexity of KMP string matching? — O(n + m), where n is text length and m is pattern length.
On a mismatch, what does KMP adjust? — Only the pattern pointer, jumping it to LPS[j-1]; the text pointer never moves backward.
Why is KMP faster than naive matching in the worst case? — It avoids re-comparing text characters already matched, giving linear instead of quadratic time.