Substring Search: Naive and Rabin-Karp

Substring search is the task of finding all occurrences of a pattern pat in text (n = len(text), m = len(pat)). The naive way costs O(nm). The Rabin-Karp algorithm compares windows not character by character but by a rolling hash and runs in O(n + m) on average. About working with strings: palindromes and anagrams.

Naive search

We place the pattern at each position i (0..n-m) and compare left to right; on a mismatch we shift by one. There are n - m + 1 positions with up to m comparisons each, so O(nm) in the worst case. In ordinary text a mismatch is found in the first characters and the time is near O(n), but on repetitive data such as aaaa...ab (DNA, binary texts) the worst case is real. Memory is O(1).

def naive(text, pat):
    n, m = len(text), len(pat)
    result, comps = [], 0
    for i in range(n - m + 1):
        j = 0
        while j < m:
            comps += 1
            if text[i + j] != pat[j]:
                break
            j += 1
        if j == m:
            result.append(i)
    return result, comps

print(naive("abracadabra", "abra"))
print(naive("a" * 20, "a" * 9 + "b"))

([0, 7], 16)
([], 110)

The rolling hash