String Matching: Prefix Tables (KMP) and Rolling Hashes

The slow way. Try the pattern at every position and compare letter by letter. On a text like aaaa...ab and a pattern like aaab, almost every try matches a long way before failing, so the cost grows like n x m. For 100,000 letters and a 50,000-letter pattern, that is billions of comparisons.

The prefix table. For each position i of the pattern, fail[i] is the length of the longest proper beginning of pattern[:i + 1] that is also its ending. For abab it is [0, 0, 1, 2]: after matching abab, the last two letters ab are also the first two. For aabaaab it is [0, 1, 0, 1, 2, 2, 3].

def prefix_table(p):
    fail = [0] * len(p)
    k = 0
    for i in range(1, len(p)):
        while k and p[i] != p[k]:
            k = fail[k - 1]       # fall back to a shorter matching border
        if p[i] == p[k]:
            k += 1
        fail[i] = k
    return fail

prefix_table('abab')   # [0, 0, 1, 2]

Searching with it. Walk the text once, keeping k, the number of pattern letters currently matched. On a mismatch, do not move back in the text: set k = fail[k - 1] and retry. On a full match, record the start and fall back the same way so overlapping matches are found. The text pointer never moves left, so the work is O(n + m).

def kmp_search(text, pat):
    fail, k, hits = prefix_table(pat), 0, []
    for i, ch in enumerate(text):
        while k and ch != pat[k]:
            k = fail[k - 1]
        if ch == pat[k]:
            k += 1
        if k == len(pat):
            hits.append(i - k + 1)
            k = fail[k - 1]
    return hits

kmp_search('ababab', 'ab')          # [0, 2, 4]
kmp_search('aaaa', 'aa')            # [0, 1, 2]
kmp_search('abcabcabd', 'abcabd')   # [3]

Why the loop is still linear. k grows by at most one per text letter, and each fall-back shrinks it, so the total number of fall-backs can never exceed the total number of increases.

Rolling hash (Rabin-Karp). Turn each window of the text into a number, for example hash = hash * base + letter taken modulo a large number. Sliding the window one step removes the old first letter and adds the new last one in O(1). If the window's hash equals the pattern's, compare the actual letters once, because different strings can share a hash. Expected O(n + m); good when searching for many patterns at once.

Gluing for prefix questions. To find the longest beginning of a word that is also an ending of another, glue them with a separator that cannot appear in either (word + '#' + other) and read the last value of the prefix table. The separator stops a match from running across the boundary. This is the trick behind 'shortest palindrome' style problems.

Where it runs in production. Searching logs and documents, plagiarism and duplicate detection (rolling hashes over chunks), intrusion-detection signatures, and the 'find' of every text editor.