KMP algorithm
- Algorithms course
- Expert
- Lesson 13/41
- 4 min
KMP string matching with a prefix table.
KMP algorithm
The KMP algorithm searches a pattern inside a text in linear time. Its complexity is O(n+m), a clear improvement over the naive O(n·m) method.
The core idea is to precompute a prefix table (lps). lps[i] is the length of the longest proper prefix of the pattern's first i+1 characters that is also a suffix.
On a mismatch we shift the pattern using the lps value instead of restarting, so we never re-compare characters we already matched.
Building the lps table
While building the lps table we use two pointers: i scans the pattern and length tracks the current matching prefix length.
If pattern[i] == pattern[length] we increment both and set lps[i] = length. On a mismatch we fall back to length = lps[length-1], reflecting the recursive nature of the prefix table.
This step runs in O(m) and scans the pattern once.
Practice kmp_search function
Write kmp_search(text, pattern). Return the first match index of the pattern in the text, or -1. Print 3 with print(kmp_search("abcabcabcd", "abcabcd")).
Starter code
def kmp_search(text, pattern):
# Return the first match indexSample solution
def kmp_search(text, pattern):
# Return the first match index
n, m = len(text), len(pattern)
lps = [0] * m
length = 0
i = 1
while i < m:
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
i = j = 0
while i < n:
if text[i] == pattern[j]:
i += 1
j += 1
if j == m:
return i - j
else:
if j != 0:
j = lps[j - 1]
else:
i += 1
return -1
print(kmp_search("abcabcabcd", "abcabcd"))Expected output
3
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What does lps[i] store?
lps = [0, 0, 0, 1, 2, 3, 0]- Total length of the pattern
- Length of the longest proper prefix that is also a suffix Correct answer
- ASCII value of the i-th text character
- Start index of the match
Explanation: lps[i] is the length of the longest proper prefix that is also a suffix.
2 lps fallback
if pattern[i] == pattern[length]:
length += 1
lps[i] = ____
i += 1if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1Explanation: lps[i] = length is set.
3 KMP concepts
| Term | Meaning |
|---|---|
lps |
Prefix table |
O(n+m) |
Linear time |
proper prefix |
Excluding the whole string |
shift |
Fall back using lps |