String matching: naive, KMP and Rabin-Karp

Searching for a word in a document is pattern matching: you have a text of length $n$ and a pattern of length $m$, and you want every position where the pattern occurs. It is a problem you can state in one sentence and optimise for decades, and the optimisations generalise into the tools behind grep, DNA alignment and plagiarism detection.

Type a text and pattern below, then step through the KMP scan and compare the work against the naive method.

Naive matching #

Line the pattern up at each position and compare characters until a mismatch, then shift by one:

def naive(text, pattern):
    for i in range(len(text) - len(pattern) + 1):
        for j in range(len(pattern)):
            if text[i + j] != pattern[j]:
                break
        else:
            yield i

The worst case is $O(nm)$ — for example, a text of all as and a pattern of as ending in b, where every alignment scans almost the whole pattern before failing.

KMP and the prefix function #

KMP preprocesses the pattern into a longest prefix-suffix (LPS) array. Entry lps[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix of it. On a mismatch at pattern index j, instead of restarting at the next text character, KMP sets j = lps[j-1] and keeps the text pointer where it is.

Because the text pointer never moves backward, the scan is $O(n)$ after an $O(m)$ preprocessing step — $O(n + m)$ overall. The LPS array is the same "reuse overlapping structure" idea that appears in data compression and string algorithms generally.

Rabin-Karp and rolling hashes #

Rabin-Karp avoids character comparisons almost entirely. It hashes the pattern and hashes each text window of length $m$, using a rolling hash so the next window's hash is computed in $O(1)$ from the previous one by removing the leading character and adding the trailing one:

$h_i = \big(h_{i-1} - t_{i-1}\,b^{\,m-1}\big)\,b + t_{i+m-1} \pmod m$

On a hash match it verifies the actual characters, because different windows can collide. Expected time is $O(n + m)$; a pathological input can force many verifications, but randomised moduli make that negligible. Rabin-Karp shines when searching for many patterns at once — hash them all and check the text's window hashes against the set.

In Python, ordinary substring search (sub in text, str.find) is implemented in C with an efficient two-way algorithm, so you rarely write KMP by hand. It matters when you need all occurrences, approximate matching, or the many-pattern case.

Where next: these primitives compose — heaps power Dijkstra, hashing powers Rabin-Karp, and every one of them rests on the asymptotic vocabulary from the start of this chapter.