Finding a pattern in text

Big idea

To find a pattern of length m in a text of length n, the simple way tries every start position — O(n × m) in the worst case. Two classic ideas cut that to O(n + m): Rabin–Karp compares cheap rolling hashes instead of strings, and KMP never moves backwards in the text because it remembers how much of the pattern it already matched.

The naive scan

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

Usually fast — most positions fail on the first character. The worst case is text "aaaa…ab" and pattern "aaab": every position matches m − 1 characters before failing. That's what str.find and indexOf might do; for interview "implement strStr" this is often the expected answer, but be ready to name the better ones.

Rabin–Karp: compare hashes

Turn each length-m window into a number, the way digits make a number: for window "cab" with a → 1, b → 2, c → 3 and base 10, the hash is 3·100 + 1·10 + 2 = 312. Sliding one step right to "abd" doesn't need a full recompute:

remove the leading 'c':  312 − 3·100 = 12
shift left:              12 × 10 = 120
add the new 'd' (4):     120 + 4 = 124

That's O(1) per slide. Compare the window hash to the pattern's hash; only when they're equal do an actual string comparison (different strings can collide on the same hash). Real code uses base 256 or 31 and takes everything modulo a large prime to keep numbers small.

def rabin_karp(text, pat, base=256, mod=1_000_000_007):
    n, m = len(text), len(pat)
    if m > n:
        return -1
    high = pow(base, m - 1, mod)          # weight of the leading char
    hp = hw = 0
    for i in range(m):
        hp = (hp * base + ord(pat[i])) % mod
        hw = (hw * base + ord(text[i])) % mod
    for i in range(n - m + 1):
        if hp == hw and text[i:i + m] == pat:
            return i
        if i + m < n:
            hw = ((hw - ord(text[i]) * high) * base + ord(text[i + m])) % mod
    return -1

Expected O(n + m). The rolling-hash trick also powers "Repeated DNA Sequences" and detecting duplicate substrings.

KMP: don't re-read the text

When a match fails after matching some characters, the naive scan throws that knowledge away. KMP precomputes, for each prefix of the pattern, the length of the longest proper prefix that is also a suffix (the "LPS" array). On a mismatch, it slides the pattern so that prefix lines up with what was just matched — the text index never goes back.

For pattern "ababc":

If you've matched "abab" and the next text character isn't c, you don't restart: you already know the text ends in "ab", which is the start of the pattern, so continue as if 2 characters are matched.

def kmp(text, pat):
    lps, k = [0] * len(pat), 0
    for i in range(1, len(pat)):
        while k and pat[i] != pat[k]:
            k = lps[k - 1]
        if pat[i] == pat[k]:
            k += 1
        lps[i] = k
    j = 0
    for i, ch in enumerate(text):
        while j and ch != pat[j]:
            j = lps[j - 1]
        if ch == pat[j]:
            j += 1
        if j == len(pat):
            return i - j + 1
    return -1

O(n + m) guaranteed: j only increases when i does, so the fall-backs are paid for (an amortized argument).

Watch it

Match ababc in abababc and watch KMP recover from a mismatch.

Which to use

Practice

• Find the Index of the First Occurrence in a String
• Repeated DNA Sequences — fixed-length windows, hashed.
• Longest Common Prefix

Quick check