Challenge 5

Final mini task: combine all modules.

Challenge 5 - Cumulative final

The fifth and final challenge combines all previous functions. count_doublings, kmp_search, convex_hull and ford_fulkerson are provided above.

You will write count_matches: given a text and a pattern, find the total number of matches using kmp_search.

This task is the last link of the cumulative chain and the final of the expert level.

Exercise count_matches function

Write count_matches(text, pattern). Using kmp_search, return the total number of matches in the text. Print 4 with print(count_matches("abababab", "ab")). The other four functions are provided above.

Show example 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
def count_matches(text, pattern):
    total = 0
    pos = 0
    while pos < len(text):
        idx = kmp_search(text[pos:], pattern)
        if idx == -1:
            break
        total += 1
        pos += idx + 1
    return total
print(count_matches("abababab", "ab"))

Test yourself

match search

idx = kmp_search(text[____:], pattern)

Show answer

idx = kmp_search(text[pos:], pattern)

Which function does count_matches use?
- kmp_search
- convex_hull
- ford_fulkerson
- count_doublings
Show answer

kmp_search — count_matches uses kmp_search to count matches.
Cumulative chain

step 1

count_doublings
step 2

kmp_search
step 3

convex_hull
step 4

ford_fulkerson

Next lesson: Expert section exam

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies