String Matching

Rolling hashes (Rabin–Karp) and the prefix function (KMP), and when to use each.

"Find a pattern in a text" can be solved with a naive O(n × m) scan, and that's often acceptable in an interview. When the interviewer asks for better, or when a problem needs to compare many substrings, two techniques cover nearly every case: rolling hashes (Rabin–Karp) and the prefix function (KMP).

Naive matching, and when it's enough

def find(text, pat):
    for i in range(len(text) - len(pat) + 1):
        if text[i:i + len(pat)] == pat:
            return i
    return -1

This is O(n × m) in the worst case ("aaaa…ab" searched for "aaab"). In Python, text.find(pat) is heavily optimized, so mention it. But be ready to implement one of the linear-time algorithms if asked.

Rolling hash (Rabin–Karp)

Treat each window of length m as a number in base B, modulo a large prime. Sliding the window removes the leading character and adds the trailing one in O(1). Equal hashes are candidates. Compare the actual strings to rule out collisions.

def rabin_karp(text, pat, base=257, mod=(1 << 61) - 1):
    n, m = len(text), len(pat)
    if m > n:
        return -1
    high = pow(base, m - 1, mod)               # weight of the leading character
    hp = ht = 0
    for i in range(m):
        hp = (hp * base + ord(pat[i])) % mod
        ht = (ht * base + ord(text[i])) % mod
    for i in range(n - m + 1):
        if hp == ht and text[i:i + m] == pat:  # verify to rule out a collision
            return i
        if i + m < n:
            ht = ((ht - ord(text[i]) * high) * base + ord(text[i + m])) % mod
    return -1

Rolling hashes really shine when you need to compare many substrings of the same length:

Repeated DNA sequences: hash every window of length 10, and look for repeats in a set.
Longest duplicate substring: binary search on the length, then check each length with rolling hashes. O(n log n).
Distinct substrings and palindrome checks with prefix hashes, giving O(1) comparisons of any two substrings.

[!WARNING] Collisions Different strings can share a hash. Either verify each match by comparing the strings, or use a very large modulus (or two independent hashes) and say that a collision is extremely unlikely. Don't ignore collisions silently. Interviewers will ask about them.

KMP and the prefix function

The prefix function pi[i] is the length of the longest proper prefix of s[:i+1] that is also a suffix of it. When a match fails, KMP uses pi to skip ahead without re-scanning the text, so the whole search is O(n + m).

def prefix_function(s):
    pi = [0] * len(s)
    k = 0
    for i in range(1, len(s)):
        while k and s[i] != s[k]:
            k = pi[k - 1]                      # fall back to the next shorter border
        if s[i] == s[k]:
            k += 1
        pi[i] = k
    return pi

def kmp_search(text, pat):
    if not pat:
        return 0
    pi = prefix_function(pat + "\0" + text)   # separator must not appear in either string
    m = len(pat)
    for i in range(m + 1, len(pi)):
        if pi[i] == m:
            return i - 2 * m
    return -1

The prefix function also solves several problems directly:

Which one to use

[!INTERVIEW] Lead with the simple solution Start with the naive scan, and state its worst case. Then offer the linear-time improvement. Writing KMP from memory without explaining why it works rarely impresses. Explaining the "fall back to the next shorter border" idea does.

[!TIP] Practice Implement strStr() · Repeated DNA Sequences · Rotate String · Longest Palindromic Substring · Substring with Concatenation of All Words