String Matching Algorithms in Python: KMP and Rabin–Karp

Finding a Needle in a Haystack

Pressing Ctrl + F in a document, searching a genome for a gene, scanning network traffic for a virus signature, or checking assignments for copied passages: all of these are string matching problems. Find every place where a short pattern occurs inside a long text. The obvious method can be very slow on large inputs, and clever algorithms do it in a single pass. This tutorial covers string matching algorithms in Python: the naive method and its worst case, the Knuth–Morris–Pratt (KMP) algorithm and its prefix function, the Rabin–Karp algorithm with a rolling hash, Python's built-in tools, and applications. It builds on the tutorials on Python strings, Big O notation and hash tables.

The Naive Method

Try every starting position in the text, and compare the pattern character by character.

def naive_search(text, pattern):
    n, m = len(text), len(pattern)
    matches = []
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            matches.append(i)
    return matches

print(naive_search("ABABDABACDABABCABAB", "ABABCABAB"))
print(naive_search("banana", "ana"))

Output:

[10]
[1, 3]

Matches can overlap: "ana" occurs at positions 1 and 3 of "banana".

Running time: in the worst case, O(n × m), for a text of length n and a pattern of length m. The worst case happens with texts like "AAAA…AAB" and patterns like "AAAB": at almost every position, the comparison runs nearly the whole length of the pattern before failing, and all that work is then thrown away.

comparisons = 0
def counting_naive(text, pattern):
    global comparisons
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):
        for j in range(m):
            comparisons += 1
            if text[i + j] != pattern[j]:
                break

counting_naive("A" * 1000, "A" * 99 + "B")
print(comparisons)

Output:

That is 90,100 character comparisons for a text of only 1,000 characters, with no match at all.

The Knuth–Morris–Pratt (KMP) Algorithm

When a mismatch happens after several characters have matched, the naive method forgets what it has learned and starts again one position later. KMP never moves backwards in the text. It uses a table, built from the pattern alone, that says how much of the pattern is still matched after a mismatch.

The prefix function

For each position i in the pattern, pi[i] is the length of the longest proper prefix of pattern[:i + 1] that is also a suffix of it. ("Proper" means not the whole string.)

For the pattern ABABCABAB:

At "ABAB" (i = 3), the prefix "AB" is also a suffix, so pi[3] = 2.
At "ABABC" (i = 4), no prefix ends in C, so pi[4] = 0.
At the whole pattern, "ABAB" is both a prefix and a suffix, so pi[8] = 4.

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

print(prefix_function("ABABCABAB"))
print(prefix_function("AAAA"))
print(prefix_function("ABCD"))

Output:

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

The search

Scan the text once, keeping track of how many pattern characters are currently matched. On a mismatch, fall back using the prefix function instead of restarting from zero.

def kmp_search(text, pattern):
    pi = prefix_function(pattern)
    matches, k = [], 0
    for i, ch in enumerate(text):
        while k > 0 and ch != pattern[k]:
            k = pi[k - 1]
        if ch == pattern[k]:
            k += 1
        if k == len(pattern):
            matches.append(i - k + 1)       # a full match ends at position i
            k = pi[k - 1]                   # keep going, to allow overlaps
    return matches

print(kmp_search("ABABDABACDABABCABAB", "ABABCABAB"))
print(kmp_search("banana", "ana"))
print(kmp_search("A" * 1000, "A" * 99 + "B"))

Output:

[10]
[1, 3]
[]

Running time: O(n + m) in every case, O(m) to build the table and O(n) to scan the text. Each step either moves forward in the text or falls back in the pattern, and the total fall-back can never exceed the total progress, so the work stays linear even on the worst-case input that slowed the naive method down.

The Rabin–Karp Algorithm

Rabin–Karp compares hash values (numbers computed from the characters) instead of comparing whole strings. If the hash of a window of text differs from the hash of the pattern, they cannot match, so the window is skipped at once. Only when the hashes agree are the characters compared, to rule out a rare collision.

The key trick is a rolling hash: when the window slides one character to the right, the new hash is computed from the old one in constant time, by removing the leftmost character's contribution and adding the new character.

The hash of a window c₀c₁…c₍ₘ₋₁₎ is (c₀ × b^(m−1) + c₁ × b^(m−2) + … + c₍ₘ₋₁₎) mod q, for a base b and a large prime q.

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 = t_hash = 0
    for i in range(m):
        p_hash = (p_hash * base + ord(pattern[i])) % mod
        t_hash = (t_hash * base + ord(text[i])) % mod
    matches = []
    for i in range(n - m + 1):
        if p_hash == t_hash and text[i:i + m] == pattern:   # confirm on a hash match
            matches.append(i)
        if i < n - m:                       # roll the window one character right
            t_hash = (t_hash - ord(text[i]) * high) % mod
            t_hash = (t_hash * base + ord(text[i + m])) % mod
    return matches

dna = "ATGCGATACGCTTGATGCGAATGCG"
print(rabin_karp(dna, "ATGCG"))
print(rabin_karp("ABABDABACDABABCABAB", "ABABCABAB"))

Output:

[0, 14, 20]
[10]

Running time: O(n + m) on average, though a poor hash with many collisions can make it slower. Rabin–Karp really shines when searching for many patterns of the same length at once: put all their hashes in a set and check each window's hash against the set. Plagiarism checkers use this idea to compare thousands of short passages against a document.

Python's Built-In Tools

For everyday programming, use Python's built-in string methods, which are implemented in fast C code using a highly optimised search algorithm.

text = "the cat sat on the mat with the hat"
print("cat" in text, text.find("the"), text.find("dog"))
print(text.count("the"), text.rfind("the"))

def find_all(text, pattern):
    positions, start = [], text.find(pattern)
    while start != -1:
        positions.append(start)
        start = text.find(pattern, start + 1)
    return positions

print(find_all(text, "at"))

import re
print([m.start() for m in re.finditer("(?=ana)", "banana")])   # overlapping matches

Output:

True 0 -1
3 28
[5, 9, 20, 33]
[1, 3]

str.count counts only non-overlapping matches, while find_all above, which restarts one position after each match, finds overlapping ones too. The regular-expression version uses a "look-ahead" (?=…) to report overlapping matches.

Applications

Text editors and search engines: find and replace, and highlighting matches.
Bioinformatics: locating genes, motifs and mutations in DNA sequences millions of letters long.
Security: intrusion-detection systems and antivirus programs scan data for known attack signatures.
Plagiarism and duplicate detection: rolling hashes of short passages ("fingerprints") let documents be compared quickly.
Data compression: compressors such as ZIP find repeated substrings to replace with short references.

Common Mistakes with String Matching

Looping to n instead of n − m + 1 in the naive method, which reads past the end of the text.
Restarting k at 0 after a full match in KMP, which misses overlapping matches. Use k = pi[k − 1].
Trusting a hash match without checking the characters in Rabin–Karp. Different strings can share a hash.
Forgetting the modulus when rolling the hash, which lets the numbers grow huge and slow everything down.
Writing your own search for ordinary tasks. Python's in, find and re are faster and well tested. Implement the algorithms to learn them, or for special needs.

String Matching: Practice Exercises

Compute the prefix function of "AABAAAB".
Use the prefix function to find the length of the longest proper prefix of "abcabcabc" that is also a suffix.
A string s is a rotation of t if both have the same length and s occurs in t + t. Write is_rotation(s, t) using kmp_search.
Use Rabin–Karp to count how many times "GAT" occurs in "GATTACAGATTAGAT".

Sample solutions:

print(prefix_function("AABAAAB"))
print(prefix_function("abcabcabc")[-1])

def is_rotation(s, t):
    return len(s) == len(t) and bool(kmp_search(t + t, s))

print(is_rotation("lolagos", "lagoslo"), is_rotation("abc", "acb"))
print(len(rabin_karp("GATTACAGATTAGAT", "GAT")))

Output:

[0, 1, 0, 1, 2, 2, 3]
6
True False
3

Conclusion

String matching finds every occurrence of a pattern in a text. The naive method tries every position and can take O(nm) time on repetitive input. KMP builds a prefix function from the pattern, so it never re-reads the text, and it runs in O(n + m) in every case. Rabin–Karp compares rolling hashes, updated in constant time per step, and confirms each hash match, which makes it ideal for searching many patterns at once. In everyday code, use Python's in, find, count and re, and use these algorithms when you need to understand what they do or to handle special cases.

String Matching Algorithms in Python: KMP and Rabin–Karp

Finding a Needle in a Haystack

The Naive Method

The Knuth–Morris–Pratt (KMP) Algorithm

The prefix function

The search

The Rabin–Karp Algorithm

Python's Built-In Tools

Applications

Common Mistakes with String Matching

String Matching: Practice Exercises

Conclusion

Related Tutorials