Implement KMP and Rabin-Karp SearchStep 4 of 5

Rabin-Karp Rolling Hash

12345

Step 4: Rabin-Karp Rolling Hash

Rabin-Karp takes a different route: hash the pattern once, then roll a hash across the text so each window costs O(1) to update.

Implement rabin_karp(text, pattern) that returns all start indices of pattern in text using a polynomial rolling hash. Use a fixed base = 256 and mod = 1000000007 so the hash is deterministic.

Because different windows can share a hash (a collision), you must confirm every hash hit with a real character comparison before recording the index.

Roll the hash by removing the leading character (multiplied by base to the power m - 1), multiplying by the base, then adding the new trailing character, all modulo mod.

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):
    n, m = len(text), len(pattern)
    if m == 0:
        return []
    lps = build_lps(pattern)
    result = []
    i = j = 0
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == m:
                result.append(i - j)
                j = lps[j - 1]
        elif j != 0:
            j = lps[j - 1]
        else:
            i += 1
    return result


def rabin_karp(text, pattern):
    """Return all start indices of pattern in text using a rolling polynomial hash."""
    # TODO: precompute pattern hash and first window hash, then roll and verify hits
    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