Implement KMP and Rabin-Karp SearchStep 3 of 5

KMP Search

12345

Step 3: KMP Search

Now use the failure array to scan the text in linear time.

Implement kmp_search(text, pattern) that returns all start indices of pattern in text, using build_lps so the text pointer never moves backward.

Walk two pointers: i over the text and j over the pattern. On a match advance both; when j reaches len(pattern) record a hit at i - j and fall back with j = lps[j - 1]. On a mismatch, if j is nonzero fall back to lps[j - 1], otherwise advance i.

Your results must match naive_search exactly on every input, including overlaps.

Hints
Starter code
def naive_search(text, pattern):
    n, m = len(text), len(pattern)
    if m == 0:
        return []
    result = []
    for i in range(n - m + 1):
        if text[i:i + m] == pattern:
            result.append(i)
    return result


def build_lps(pattern):
    m = 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
    return lps


def kmp_search(text, pattern):
    """Return all start indices of pattern in text using the lps array."""
    # TODO: advance i and j, recording a hit at i - j when j reaches len(pattern)
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step