String Algorithms: KMP and Rabin-Karp

Learn string matching algorithms in Python: naive search, the KMP prefix function and Rabin-Karp rolling hashes, with time complexity for each.

• Advanced
• 20 min read
• 4 objectives

Before this lessonLesson 15: Bit Manipulation

Finding a pattern inside a larger text is one of the oldest problems in computing: the search box in your editor, grep, DNA sequence analysis, plagiarism checks and intrusion detection all do it. The text has length n and the pattern length m. This lesson covers the naive method and two classic improvements, KMP (Knuth-Morris-Pratt) and Rabin-Karp, each with a different clever idea.

The naive approach and its worst case

Try every starting position and compare character by character. It is simple and usually fine, but on repetitive input it re-checks the same characters again and again.

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

print(naive_find_all("stackcone learns, stackcone ships", "stackcone"))
print(naive_find_all("a" * 1000, "a" * 99 + "b")[1], "comparisons")

([0, 18], 42)
90100 comparisons

That second call does about 90,000 comparisons for a 1,000-character text. Worst case O(n * m) time, O(1) space. When the mismatch happens at the last character of the pattern, the naive method throws away everything it just learned and starts again at i + 1.

KMP: never re-read the text

KMP's insight: when a mismatch happens after matching j characters, you already know what those characters were (they equal the pattern's first j characters). If the pattern's matched part ends with something that is also a prefix of the pattern, you can keep that overlap and continue, without moving back in the text.

Precompute, for each position i in the pattern, the length of the longest proper prefix of pat[:i+1] that is also a suffix of it. This is the prefix function (also called the failure table or LPS array).

def prefix_function(pat):
    pi = [0] * len(pat)
    k = 0                           # length of current matching prefix
    for i in range(1, len(pat)):
        while k > 0 and pat[i] != pat[k]:
            k = pi[k - 1]           # fall back to a shorter border
        if pat[i] == pat[k]:
            k += 1
        pi[i] = k
    return pi

print(prefix_function("ababaca"))
print(prefix_function("aabaaab"))

[0, 0, 1, 2, 3, 0, 1]
[0, 1, 0, 1, 2, 2, 3]

For "ababaca", pi[4] = 3 because "ababa" starts and ends with "aba". Now the search uses the table exactly the same way: on mismatch, fall back to pi[j - 1] instead of restarting.

# from earlier in this lesson
def prefix_function(pat):
    pi = [0] * len(pat)
    k = 0                           # length of current matching prefix
    for i in range(1, len(pat)):
        while k > 0 and pat[i] != pat[k]:
            k = pi[k - 1]           # fall back to a shorter border
        if pat[i] == pat[k]:
            k += 1
        pi[i] = k
    return pi

# new code
def kmp_find_all(text, pat):
    pi = prefix_function(pat)
    hits, j = [], 0
    for i, ch in enumerate(text):
        while j > 0 and ch != pat[j]:
            j = pi[j - 1]
        if ch == pat[j]:
            j += 1
        if j == len(pat):
            hits.append(i - len(pat) + 1)
            j = pi[j - 1]           # allow overlapping matches
    return hits

print(kmp_find_all("abababab", "abab"))
print(kmp_find_all("a" * 1000, "a" * 99 + "b"))
print(kmp_find_all("stackcone learns, stackcone ships", "stackcone"))

[0, 2, 4]
[]
[0, 18]

The index i only moves forward, and j can only fall back as many times as it has increased, so the total work is linear. Time O(n + m), space O(m) for the table.

Rabin-Karp: compare hashes, not strings

Rabin-Karp takes a different route. Turn each length-m window of the text into a number (a hash) and compare it with the pattern's hash. Numbers compare in O(1). The trick is a rolling hash: when the window slides one step, update the hash in O(1) by removing the leaving character and adding the new one, like the sliding window sum.

Treat the window as a number in base B (say 256) modulo a large prime M. To slide: subtract the leading character times B^m-1, multiply by B, add the new character.

def rabin_karp(text, pat, base=256, mod=1_000_000_007):
    n, m = len(text), len(pat)
    if m > n:
        return []
    high = pow(base, m - 1, mod)          # weight of the leading char
    p_hash = t_hash = 0
    for i in range(m):
        p_hash = (p_hash * base + ord(pat[i])) % mod
        t_hash = (t_hash * base + ord(text[i])) % mod
    hits = []
    for i in range(n - m + 1):
        if t_hash == p_hash and text[i:i + m] == pat:   # verify on hash hit
            hits.append(i)
        if i + m < n:
            t_hash = (t_hash - ord(text[i]) * high) % mod
            t_hash = (t_hash * base + ord(text[i + m])) % mod
    return hits

print(rabin_karp("abababab", "abab"))
print(rabin_karp("the cat sat on the mat", "at"))

[0, 2, 4]
[5, 9, 20]

Two different strings can share a hash (a collision), which is why the code double-checks with a real comparison. With a large prime, collisions are rare, so the expected time is O(n + m); the worst case, with an adversary forcing collisions, is O(n * m). Space O(1).

Rabin-Karp's real strength is searching for many patterns of the same length at once (put all pattern hashes in a set) and finding repeated substrings. For example, finding any duplicated 10-letter sequence in a DNA string:

def repeated_substrings(s, k):
    seen, repeats = set(), set()
    for i in range(len(s) - k + 1):
        chunk = s[i:i + k]          # Python hashes the slice for us
        if chunk in seen:
            repeats.add(chunk)
        seen.add(chunk)
    return sorted(repeats)

print(repeated_substrings("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT", 10))

['AAAAACCCCC', 'CCCCCAAAAA']

This version leans on Python's built-in hashing of each slice (O(k) per step); a true rolling hash makes each step O(1), which matters when k is large.

Comparison

• Naive: O(n * m) worst case, O(1) space, fine for short patterns and normal text.
• KMP: O(n + m) guaranteed, O(m) space, never moves backwards in the text (good for streams).
• Rabin-Karp: O(n + m) expected, O(1) space, great for multiple patterns and duplicate detection.
• Built-in str.find: the practical default in Python.

Recap

• Naive matching restarts after every mismatch, costing O(n * m) on repetitive input.
• The KMP prefix function records the longest border of each pattern prefix.
• KMP falls back using that table and never re-reads the text: O(n + m).
• Rabin-Karp compares rolling hashes in O(1) per step and verifies on a match.
• Hash collisions are possible, so always confirm a hash hit with a real comparison.

# Write your solution here