Summary - String matching
- Algorithms course
- Expert
- Lesson 18/41
- 4 min
Print the match index with KMP in a mini task.
Summary - String matching
In this group we covered five string matching methods: KMP, Rabin-Karp, Boyer-Moore, Z-algorithm and suffix array.
KMP uses a prefix table, Rabin-Karp a rolling hash, Boyer-Moore the bad character rule, all in linear time. The Z-algorithm and suffix array support broader tasks.
We will now revisit KMP with a small task.
Practice kmp_search mini task
Write kmp_search(text, pattern). Return the first match index, or -1. Print 1 with print(kmp_search("mississippi", "issi")).
Starter code
def kmp_search(text, pattern):
# First match with KMPSample solution
def kmp_search(text, pattern):
# First match with KMP
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("mississippi", "issi"))Expected output
1
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Which method has no hash collision risk?
- Rabin-Karp
- Boyer-Moore bad character
- KMP Correct answer
- Rolling hash
Explanation: KMP does not use hashing, so no collision risk.
2 KMP lps value
Question
# pattern = "abcabd"
# lps[4] = ____
Answer
# pattern = "abcabd"
# lps[4] = 2Explanation: lps[4] = 2 ("ab" is both prefix and suffix).
3 Method-property
| Term | Meaning |
|---|---|
KMP |
Prefix table |
Rabin-Karp |
Rolling hash |
Boyer-Moore |
Bad character |
Z-algorithm |
Z-array |