Algorithms
KMP algorithm
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.
Exercise 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")).
Show example 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"))
Test yourself
-
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
- ASCII value of the i-th text character
- Start index of the match
Show answer
Length of the longest proper prefix that is also a suffix — lps[i] is the length of the longest proper prefix that is also a suffix.
-
lps fallback
if pattern[i] == pattern[length]:
length += 1
lps[i] = ____
i += 1
Show answer
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
-
KMP concepts
- lps
- Prefix table
- O(n+m)
- Linear time
- proper prefix
- Excluding the whole string
- shift
- Fall back using lps
Next lesson: Rabin-Karp
