Challenge 2
- Algorithms course
- Expert
- Lesson 38/41
- 4 min
Print the KMP match index.
Challenge 2 - KMP
The second challenge tests the KMP string matching algorithm. Using the prefix table (lps) it searches a pattern in a text in linear time.
The count_doublings function above is already provided; you will write kmp_search. Build the lps table first, then scan with two pointers.
This challenge is the second link of the cumulative chain.
Practice kmp_search function
Write kmp_search(text, pattern). Return the first match index, or -1. Print 3 with print(kmp_search("abcabcabcd", "abcabcd")). The count_doublings function is provided above.
Starter code
def count_doublings(n):
count = 0
size = 1
last = 0
for i in range(n):
if last == size:
size *= 2
count += 1
last += 1
return count
def kmp_search(text, pattern):
# İlk eşleşme indeksini döndürSample solution
def kmp_search(text, pattern):
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
elif 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
elif 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 lps table
Question
lps = [0] * ____
length = 0
Answer
lps = [0] * m
length = 0Explanation: lps has length m, the pattern length.
2 KMP concepts
| Term | Meaning |
|---|---|
lps |
Prefix table |
O(n+m) |
Linear time |
i - j |
Match index |
-1 |
No match |
3 What is the complexity of KMP?
- O(n·m)
- O(n+m) Correct answer
- O(n²)
- O(2ⁿ)
Explanation: KMP runs in O(n+m).