Implement KMP and Rabin-Karp SearchStep 5 of 5

Repeated Substring Detection

12345

Step 5: Repeated Substring Detection

Plagiarism detectors and de-duplicators ask a different question: does any chunk of text repeat? The rolling hash answers it fast.

Implement has_repeated_substring(s, k) that returns True if any length-k substring of s appears at more than one starting index, and False otherwise.

Roll a hash of every length-k window (same fixed base = 256 and mod = 1000000007) and remember the windows you have seen in a set or dict keyed by hash. On a hash collision, verify the actual substrings are equal before declaring a repeat.

Return False when k is not a valid window size (k <= 0 or k > len(s)).

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):
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []
    base = 256
    mod = 1000000007
    high = pow(base, m - 1, mod)
    ph = 0
    th = 0
    for i in range(m):
        ph = (ph * base + ord(pattern[i])) % mod
        th = (th * base + ord(text[i])) % mod
    result = []
    for i in range(n - m + 1):
        if ph == th and text[i:i + m] == pattern:
            result.append(i)
        if i < n - m:
            th = ((th - ord(text[i]) * high) * base + ord(text[i + m])) % mod
    return result


def has_repeated_substring(s, k):
    """Return True if any length-k substring of s occurs more than once."""
    # TODO: roll a length-k hash across s and detect a verified repeat via a dict
    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.

PreviousAll challenges