Implement KMP and Rabin-Karp SearchStep 2 of 5

KMP Failure Function

12345

Step 2: KMP Failure Function

Naive search wastes work: after a mismatch it throws away everything it learned. Knuth-Morris-Pratt fixes this with a precomputed table.

Implement build_lps(pattern) that returns the longest proper prefix which is also a suffix array (the LPS or failure array). lps[i] is the length of the longest proper prefix of pattern[0 : i + 1] that is also a suffix of it.

For pattern ababaca the answer is [0, 0, 1, 2, 3, 0, 1].

This table lets KMP know how far to shift the pattern after a mismatch without re-examining text characters.

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):
    """Return the KMP longest-proper-prefix-suffix array for pattern."""
    # TODO: track the current prefix length and fall back via lps on mismatch
    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