KMP String Matching
DSA · Classic Algorithms
Theory
The Knuth-Morris-Pratt (KMP) algorithm finds every occurrence of a pattern inside a text in O(n + m) time. The naive approach slides the pattern one position at a time and can recompare the same characters again and again, costing O(n * m). KMP avoids this by precomputing an LPS array (longest proper prefix that is also a suffix) for the pattern. When a mismatch happens after matching some characters, the LPS value tells how many of those characters are already known to match the start of the pattern, so the search continues without moving backwards in the text. Building the LPS array takes O(m) and scanning the text takes O(n).
Why we use it
Fast pattern search is used in text editors, search tools like grep, DNA analysis and log scanning. KMP is also a common interview topic that tests understanding of prefix functions.
When to use it
Use KMP when you need guaranteed linear-time search, especially for repetitive patterns or streaming text. In everyday Python, str.find and the re module are usually enough.
How it works
- Build LPS table for the pattern
- For each character in text
- Character matches pattern[j]? Yes: j = j + 1. No: If j > 0: j = lps[j-1], compare again.
- j == pattern length? Yes: Match found; j = lps[j-1]. No: Continue.
- O(n + m)
Syntax
Build LPS for pattern O(m)
Scan text using LPS on mismatch O(n)
Total O(n + m)Example
def build_lps(p):
lps, length = [0] * len(p), 0
for i in range(1, len(p)):
while length and p[i] != p[length]:
length = lps[length - 1]
if p[i] == p[length]:
length += 1
lps[i] = length
return lps
def kmp_search(text, p):
lps, j, found = build_lps(p), 0, []
for i, ch in enumerate(text):
while j and ch != p[j]:
j = lps[j - 1]
if ch == p[j]:
j += 1
if j == len(p):
found.append(i - j + 1)
j = lps[j - 1]
return found
print("LPS of ABABCABAB:", build_lps("ABABCABAB"))
print("Matches:", kmp_search("ABABDABACDABABCABAB", "ABABCABAB"))
print("Overlapping:", kmp_search("aaaaa", "aa"))
log = "ERROR disk ... INFO ok ... ERROR timeout"
print("ERROR at:", kmp_search(log, "ERROR"))Key points
- Precompute the LPS (prefix-suffix) table for the pattern
- Never moves backwards in the text
- O(n + m) total time
- Finds overlapping matches too