String Algorithms: KMP & Rabin–Karp

The pattern matching problem#

Given a text of length n and a pattern of length m, find every position where the pattern occurs. It's behind Ctrl+F, grep, plagiarism checkers, DNA sequence analysis, intrusion detection systems and search engines.

The naive approach: O(n · m)#

Try every starting position and compare character by character:

def naive_search(text, pattern):
    matches, comparisons = [], 0
    for start in range(len(text) - len(pattern) + 1):
        for j in range(len(pattern)):
            comparisons += 1
            if text[start + j] != pattern[j]:
                break
        else:
            matches.append(start)
    return matches, comparisons

print(naive_search("ABABDABACDABABCABAB", "ABABCABAB"))
print(naive_search("A" * 30 + "B", "A" * 9 + "B"))

Output:

([10], 29)
([21], 220)

On ordinary text the naive search is fine — mismatches happen quickly. But on repetitive input (the second example) it re-examines the same characters again and again: after matching nine As and failing, it shifts by one and compares eight of them again. Worst case: O(n · m).

Knuth–Morris–Pratt (KMP): O(n + m)#

KMP never moves backwards in the text. When a mismatch happens, it uses what it already knows about the pattern to skip ahead.

The LPS (prefix function) table#

For each position i in the pattern, lps[i] is the length of the longest proper prefix of pattern[:i+1] that is also a suffix of it.

At i = 3, "ABAB" ends with "AB" which is also its prefix, so lps[3] = 2. If we've matched ABAB and the next character mismatches, we know the last two characters AB already match the start of the pattern — so we continue comparing from pattern index 2 instead of starting over.

def build_lps(pattern):
    lps = [0] * len(pattern)
    length = 0                       # length of the current matching prefix
    for i in range(1, len(pattern)):
        while length and pattern[i] != pattern[length]:
            length = lps[length - 1]     # fall back to a shorter prefix
        if pattern[i] == pattern[length]:
            length += 1
        lps[i] = length
    return lps

def kmp_search(text, pattern):
    lps, matches, j, comparisons = build_lps(pattern), [], 0, 0
    for i, ch in enumerate(text):        # i only ever moves forward
        while j and ch != pattern[j]:
            comparisons += 1             # a failed comparison…
            j = lps[j - 1]               # …falls back, reusing what already matched
        comparisons += 1
        if ch == pattern[j]:
            j += 1
            if j == len(pattern):
                matches.append(i - j + 1)
                j = lps[j - 1]           # keep searching for overlapping matches
    return matches, comparisons

print(build_lps("ABABCABAB"))
print(kmp_search("ABABDABACDABABCABAB", "ABABCABAB"))
print(kmp_search("A" * 30 + "B", "A" * 9 + "B"))
print(kmp_search("AAAAA", "AA"))

Output:

[0, 0, 1, 2, 0, 1, 2, 3, 4]
([10], 23)
([21], 52)
([0, 1, 2, 3], 5)

On the repetitive input, KMP needs 52 comparisons instead of 220, and it finds overlapping matches. Building the LPS table is O(m) and the search is O(n), so KMP is O(n + m) in the worst case.

Rabin–Karp: rolling hashes#

Rabin–Karp compares hashes instead of characters. It computes a hash of the pattern and of each window of the text; only when hashes match does it compare the actual strings (to rule out collisions).

The trick is a rolling hash: moving the window one character to the right updates the hash in O(1) — remove the leftmost character's contribution, shift, add the new character.

def rabin_karp(text, pattern, base=256, mod=1_000_000_007):
    n, m = len(text), len(pattern)
    if m > n:
        return []
    high = pow(base, m - 1, mod)                 # weight of the leftmost character
    p_hash = w_hash = 0
    for i in range(m):
        p_hash = (p_hash * base + ord(pattern[i])) % mod
        w_hash = (w_hash * base + ord(text[i])) % mod

    matches = []
    for start in range(n - m + 1):
        if w_hash == p_hash and text[start:start + m] == pattern:   # verify to rule out collisions
            matches.append(start)
        if start + m < n:                                           # roll the window one step right
            w_hash = (w_hash - ord(text[start]) * high) % mod
            w_hash = (w_hash * base + ord(text[start + m])) % mod
    return matches

print(rabin_karp("ABABDABACDABABCABAB", "ABABCABAB"))
print(rabin_karp("the cat sat on the mat with the hat", "the"))

Output:

[10]
[0, 15, 28]

Complexity: O(n + m) on average; O(n · m) in the worst case if many hash collisions occur (rare with a large prime modulus). Rabin–Karp shines when searching for many patterns at once (hash them all into a set) and is the idea behind plagiarism detection and the rolling checksums in rsync and content-defined chunking for backups.

Comparison#

In practice, use your language's built-in search (str.find, in, indexOf) — they're highly optimised. Learn KMP and Rabin–Karp for interviews and for problems that build on them, such as longest repeated substring, shortest palindrome and detecting repeated DNA sequences.

Common mistakes#

• Resetting the pattern index to 0 on mismatch in KMP — use lps[j - 1].
• Negative values from the rolling hash in languages without Python's modulo behaviour — add mod before taking %.
• Trusting hash equality in Rabin–Karp without verifying the substring.
• Off-by-one window bounds — the last starting index is n - m.

Key takeaways#

• Naive search is O(n · m) and slows down badly on repetitive input.
• KMP uses the LPS table to avoid re-checking characters, guaranteeing O(n + m).
• Rabin–Karp compares rolling hashes in O(1) per step and verifies matches.
• Built-in string search is best in production; these algorithms power harder problems.