1. One-Liner
Knuth–Morris–Pratt (KMP) finds every occurrence of a pattern in a text in O(n + m) by never re-checking text characters that already matched, using a longest proper prefix which is also suffix (LPS) table.
2. The Problem It Solves
Given text T of length n and pattern P of length m, find all starting indices where P occurs in T. Naive backtracking can take O(n·m) when the pattern has repeated prefixes; KMP avoids re-scanning T.
3. The Core Idea
When a mismatch happens after matching a prefix of P, you do not slide P by only one character blindly. The LPS tells you the longest prefix of P that is already aligned with the suffix of the matched portion, so you resume comparing from the next meaningful position in P.
4. How It Works (Table)
| Step | What Happens |
|---|---|
| 1. Build LPS | For each index i in P, lps[i] = length of longest proper prefix of P[0..i] that is also a suffix of P[0..i]. |
| 2. Two pointers | i scans T, j scans P. |
| 3. Match | If T[i] == P[j], advance both. If j == m, record a match and set j = lps[j-1]. |
| 4. Mismatch | If j > 0, set j = lps[j-1] (no i move). If j == 0, increment i. |
5. Dry Run Example
T = "ABABDABACD", P = "ABA". LPS for "ABA": [0,0,1]. Scan: match ABA at index 0; then shift using LPS. KMP avoids rechecking T from scratch after partial overlaps.
6. Key Properties
| Property | Value |
|---|---|
| Time | O(n + m) |
| Space | O(m) for LPS |
| Online | Can stream text with same machinery |
| Deterministic | No hashing; exact character comparison |
7. Where It Is Used
| Domain | Use |
|---|---|
| Bioinformatics | DNA motif scanning in long sequences |
| Editors / IDEs | Incremental search, syntax highlighting engines |
| Networking | Pattern filters in packet inspection (alongside other algos) |
8. Interview Tips
Derive why lps[j-1] on mismatch: longest border of the matched prefix. Contrast with Rabin–Karp (hashing) and Z-function (related self-similarity). Watch empty pattern and overlap outputs.
9. Comparison with Other Algorithms
| Algorithm | Time | Notes |
|---|---|---|
| Naive | O(n·m) worst | Simple, many rescan |
| KMP | O(n + m) | No hash; good for repetitive patterns |
| Rabin–Karp | O(n + m) average | Multiple patterns with rolling hash |
| Boyer–Moore | Sublinear often | Skips from end of pattern |
10. Complexity
| Metric | Value |
|---|---|
| Preprocess (LPS) | O(m) time, O(m) space |
| Search | O(n) time |
| Total | O(n + m) time, O(m) extra space |
Implementation Example (PYTHON)
def kmp_search(text, pat):
if not pat:
return list(range(len(text) + 1))
m = len(pat)
lps = [0] * m
length, i = 0, 1
while i < m:
if pat[i] == pat[length]:
length += 1
lps[i] = length
i += 1
elif length:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
out, j = [], 0
for i in range(len(text)):
while j and text[i] != pat[j]:
j = lps[j - 1]
if text[i] == pat[j]:
j += 1
if j == m:
out.append(i - m + 1)
j = lps[j - 1]
return out