String Matching: KMP & Rolling Hash

Every search box, log filter, spam checker and DNA tool has to answer the same question: where does this pattern appear in this text? Python's in and str.find() answer it for you, and in real code you should use them. But interviews ask how it works, and some problems (searching many patterns at once, comparing substrings by hash, finding repeated pieces) need the ideas underneath.

This lesson builds on String Problems. You will see why the simple method can be slow, then learn two classic algorithms: KMP (Knuth, Morris and Pratt), which never re-reads the text, and Rabin-Karp, which compares fingerprints called rolling hashes.

Naive search and its worst case

The simple method tries every starting position and compares the pattern character by character. With text length n and pattern length m, that is O(n × m) in the worst case. Normal English text rarely hits the worst case, because a mismatch usually comes quickly. Repetitive data, such as log lines or DNA, can.

def naive_search(text, pattern):
    positions, comparisons = [], 0
    for start in range(len(text) - len(pattern) + 1):
        k = 0
        while k < len(pattern):
            comparisons += 1
            if text[start + k] != pattern[k]:
                break
            k += 1
        if k == len(pattern):
            positions.append(start)
    return positions, comparisons

print(naive_search("the bus to pune left the bus stand", "bus"))
text, pattern = "a" * 1000, "a" * 99 + "b"
print(naive_search(text, pattern)[1], "comparisons for", len(text), "characters")

([4, 25], 36)
90100 comparisons for 1000 characters

The second search re-checks almost the same 99 characters at each of 901 positions. The work done at one position is thrown away at the next. KMP keeps it.

The KMP prefix function

KMP first studies the pattern alone. 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 "abcab", the last value is 2, because "ab" is both a prefix and a suffix of "abcab".

Why does this help? Suppose you have matched "abcab" and the next character fails. You know the last two characters read were "ab", which is also how the pattern starts. So you can continue as if 2 characters are already matched, without moving back in the text.

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

for word in ["abcab", "aabaaab", "nanana", "rohtak"]:
    print(f"{word:8} {prefix_function(word)}")

abcab    [0, 0, 0, 1, 2]
aabaaab  [0, 1, 0, 1, 2, 2, 3]
nanana   [0, 0, 1, 2, 3, 4]
rohtak   [0, 0, 0, 0, 0, 0]

A prefix that is also a suffix is called a border. The while loop tries the next shorter border when extending fails. Even though it is a loop inside a loop, the total work is O(m): k rises by at most 1 per step and every fall-back lowers it, so it can only fall as much as it has risen.

KMP search

The search uses the same loop, with the text in place of the pattern. When k reaches the pattern length, a match ends here; then fall back with pi to keep finding overlapping matches.

def prefix_function(p):
    pi, k = [0] * len(p), 0
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:
            k = pi[k - 1]
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi

def kmp_search(text, pattern):
    pi, k = prefix_function(pattern), 0
    positions, comparisons = [], 0
    for i, ch in enumerate(text):
        while k > 0 and ch != pattern[k]:
            comparisons += 1
            k = pi[k - 1]
        comparisons += 1
        if ch == pattern[k]:
            k += 1
        if k == len(pattern):
            positions.append(i - k + 1)
            k = pi[k - 1]                 # allow overlapping matches
    return positions, comparisons

print(kmp_search("the bus to pune left the bus stand", "bus")[0])
print(kmp_search("nananana", "nana")[0])
text, pattern = "a" * 1000, "a" * 99 + "b"
print(kmp_search(text, pattern)[1], "comparisons for", len(text), "characters")

[4, 25]
[0, 2, 4]
1901 comparisons for 1000 characters

The text pointer i never moves backwards, so KMP is O(n + m) in every case: 1,901 comparisons instead of 90,100. The second line shows overlapping matches of "nana", which str.count() would not report, because it counts non-overlapping matches only.

Rabin-Karp: compare fingerprints

Rabin-Karp turns each window of the text into a number, a hash, and compares numbers instead of strings. A polynomial hash treats the characters as digits in a large base B, modulo a large prime M. The trick is the rolling update: when the window slides one place, remove the leaving character's contribution and add the new one in O(1), instead of rehashing m characters.

Equal strings always have equal hashes, but different strings can occasionally share a hash (a collision). So when the hashes match, confirm with a real comparison.

B, M = 257, (1 << 61) - 1          # base and a large prime modulus

def rabin_karp(text, pattern):
    m = len(pattern)
    if m > len(text):
        return []
    high = pow(B, m - 1, M)        # weight of the leftmost character
    hp = ht = 0
    for i in range(m):
        hp = (hp * B + ord(pattern[i])) % M
        ht = (ht * B + ord(text[i])) % M
    found = []
    for start in range(len(text) - m + 1):
        if ht == hp and text[start:start + m] == pattern:   # confirm on a hash match
            found.append(start)
        if start + m < len(text):                           # roll the window
            ht = ((ht - ord(text[start]) * high) * B + ord(text[start + m])) % M
    return found

log = "GET /cart 200; GET /pay 500; GET /cart 200; GET /pay 500"
print(rabin_karp(log, "/pay 500"))
print(rabin_karp("abababab", "abab"))

[19, 48]
[0, 2, 4]

The expected time is O(n + m). Its real strength is many patterns of the same length: put all the pattern hashes in a set and slide over the text once, checking each window's hash against the set. Plagiarism checkers and duplicate-detection tools use this idea to find shared passages, and the rsync file-sync tool uses a rolling checksum to find blocks a file already has.

Advanced: longest repeated substring

What is the longest piece of text that appears at least twice? If a repeat of length L exists, a repeat of every shorter length exists too, so the condition is monotonic and you can use binary search on the answer. For each candidate length, slide a rolling hash and look for a hash seen before.

B, M = 257, (1 << 61) - 1

def repeat_of_length(s, L):
    if L == 0:
        return ""
    high = pow(B, L - 1, M)
    h = 0
    for ch in s[:L]:
        h = (h * B + ord(ch)) % M
    seen = {h: 0}
    for start in range(1, len(s) - L + 1):
        h = ((h - ord(s[start - 1]) * high) * B + ord(s[start + L - 1])) % M
        if h in seen and s[seen[h]:seen[h] + L] == s[start:start + L]:
            return s[start:start + L]
        seen.setdefault(h, start)
    return None

def longest_repeat(s):
    lo, hi, best = 1, len(s) - 1, ""
    while lo <= hi:
        mid = (lo + hi) // 2
        found = repeat_of_length(s, mid)
        if found is not None:
            best, lo = found, mid + 1
        else:
            hi = mid - 1
    return best

print(repr(longest_repeat("banana")))
print(repr(longest_repeat("jaipur to pune, pune to jaipur")))
print(repr(longest_repeat("abcd")))

'ana'
'jaipur'
''

Each check is O(n) expected and binary search adds a log n factor, so the whole thing is O(n log n). A suffix array or suffix automaton can do it in O(n), but this version is much easier to write in an interview. Note that the repeats may overlap, as "ana" does in "banana".

Common mistakes

• Trusting a hash match without checking the strings, which reports false matches after a collision.
• Forgetting the modulus in a rolling hash; in Java or C++, intermediate products also overflow 64 bits, so use a smaller modulus or 128-bit arithmetic.
• Resetting k to 0 after a KMP match, which misses overlapping matches. Use k = pi[k - 1].
• Off-by-one in the prefix function: pi[0] is always 0, and the loop starts at index 1.
• Writing your own search in production. Use in, find() or the re module unless you need something they cannot do.

Key points

• Naive search is O(n × m) in the worst case, on repetitive text.
• The prefix function stores, for each prefix of the pattern, its longest border; it is built in O(m).
• KMP never moves backwards in the text and runs in O(n + m) always.
• Rabin-Karp compares rolling polynomial hashes and confirms real matches; it shines with many same-length patterns.
• Binary search on length plus rolling hashes finds the longest repeated substring in O(n log n).
• Never use Python's randomised hash() for stored fingerprints.

def prefix_function(p):
    pi, k = [0] * len(p), 0
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:
            k = pi[k - 1]
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi

def shortest_period(s):
    n = len(s)
    p = n - prefix_function(s)[-1]
    return s[:p] if n % p == 0 else s

for word in ["abcabcabc", "aaaa", "abcab", "tiktiktik"]:
    print(word, "->", shortest_period(word))

abcabcabc -> abc
aaaa -> a
abcab -> abcab
tiktiktik -> tik