String Matching: Rabin–Karp and KMP

The problem: finding a needle in a haystack

String matching asks a simple question: does one string, the pattern (the “needle”), appear somewhere inside another string, the text (the “haystack”)? And if so, at what index does the first match start? This is exactly what "hello world".find("world") does in Python, returning 6.

Two lengths control the cost. We call the text length n and the pattern length m. A match is a stretch of m consecutive characters in the text that equals the pattern, so the only possible starting positions are 0 through n - m.

We measure cost with Big-O notation, which describes how the work grows with the input size. The methods below range from O(n·m) (slow when both strings are long) down to O(n + m) (each character looked at a constant number of times). The whole art of fast string matching is avoiding wasted re-reading of characters you have already seen.

Naive search and why it repeats work

The direct method tries every possible starting position and, at each one, compares the pattern character by character until it either matches fully or hits a mismatch.

def naive_search(text, pattern):
    n, m = len(text), len(pattern)
    for start in range(n - m + 1):        # every place the pattern could begin
        k = 0
        while k < m and text[start + k] == pattern[k]:
            k += 1                        # characters agree so far; keep going
        if k == m:                        # ran through the whole pattern
            return start
    return -1                             # no start position matched

print(naive_search("hello world", "world"))   # -> 6
print(naive_search("aaaaab", "aab"))           # -> 3
print(naive_search("abc", "xyz"))              # -> -1

Complexity. There are up to n - m + 1 starting positions, and each inner comparison can run up to m characters, so the worst case is O(n·m) time and O(1) space. That worst case is real, not just theoretical: on text = "aaaaaaaaab" and pattern = "aaaab", almost every start matches four as before failing on the fifth character, so the inner loop nearly runs to m every single time.

The waste is the key insight. When the comparison fails after matching several characters, naive search throws that knowledge away and slides the pattern forward by just one, re-reading text it has already seen. The two classic algorithms below each cache what was learned so the scan can move forward without backtracking.

Rabin–Karp: hashing a sliding window

Rabin–Karp turns the “does this window equal the pattern?” question into “do their hashes match?” A hash is a single number computed from a string. If we can compute the hash of each m-character window cheaply, we replace an m-character comparison with one integer comparison.

The trick is a rolling hash: treat the window as a number in a large base (like a base-256 number whose digits are the character codes). When the window slides one step right, we do not recompute from scratch. We subtract the contribution of the character leaving on the left, shift up by one digit, and add the new character on the right — all in O(1).

flowchart LR
    A["window: a b c<br/>hash H"] -->|"drop 'a', add 'd'"| B["window: b c d<br/>hash H'"]
    B -->|"drop 'b', add 'e'"| C["window: c d e<br/>hash H''"]

Because different strings can collide (share a hash), a hash match is only a candidate. We confirm it with a direct character comparison. Collisions are rare with a large prime modulus, so the confirmation almost never runs.

def rabin_karp(text, pattern):
    n, m = len(text), len(pattern)
    if m == 0:
        return 0
    if m > n:
        return -1
    base = 256               # treat each character code as a digit in base 256
    mod = 1_000_000_007      # a large prime keeps the numbers small and collisions rare
    high = pow(base, m - 1, mod)   # base^(m-1) % mod: the weight of the leftmost digit

    p_hash = 0               # hash of the pattern
    t_hash = 0               # hash of the current text window
    for i in range(m):       # hash the pattern and the first window together
        p_hash = (p_hash * base + ord(pattern[i])) % mod
        t_hash = (t_hash * base + ord(text[i])) % mod

    for start in range(n - m + 1):
        if p_hash == t_hash:                        # candidate: verify to rule out a collision
            if text[start:start + m] == pattern:
                return start
        if start < n - m:                           # roll the window one step right
            left = ord(text[start])                 # character leaving on the left
            t_hash = (t_hash - left * high) % mod    # drop it
            t_hash = (t_hash * base + ord(text[start + m])) % mod   # shift up, add the new right char
    return -1

print(rabin_karp("hello world", "world"))   # -> 6
print(rabin_karp("mississippi", "issip"))    # -> 4
print(rabin_karp("abc", "xyz"))              # -> -1

The % mod after every step keeps the hash from growing into a huge integer. Python’s % always returns a non-negative result, so the subtraction (t_hash - left * high) % mod stays correct even when the intermediate value goes negative. pow(base, m - 1, mod) is Python’s fast modular exponentiation: it computes base to the power m - 1 modulo mod without building the giant number in between.

Complexity. Building the initial hashes is O(m), and rolling across the text is O(n), so the average case is O(n + m) time with O(1) space. The worst case degrades to O(n·m) if hashes collide on nearly every window and the verification keeps running — but with a good large prime that essentially never happens on real input. Rabin–Karp also shines when searching for many patterns of the same length at once: hash them all, then compare each window’s hash against the set.

KMP: remembering the needle’s own overlaps

The Knuth–Morris–Pratt algorithm removes the wasted re-reading a different way: it never moves backward in the text at all. When a mismatch happens after matching a prefix of the pattern, KMP asks a question it can answer ahead of time — “how much of what I just matched is also a prefix of the pattern?” — and slides the pattern forward by exactly that much, keeping the already-matched suffix aligned.

That knowledge is precomputed into the longest-prefix-suffix table, lps. For each position i, lps[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.) It depends only on the pattern, so we build it once.

def build_lps(pattern):
    lps = [0] * len(pattern)
    length = 0                              # length of the current longest border
    for i in range(1, len(pattern)):
        while length > 0 and pattern[i] != pattern[length]:
            length = lps[length - 1]        # mismatch: fall back to the next-best border
        if pattern[i] == pattern[length]:
            length += 1                     # extend the border by one
        lps[i] = length
    return lps

print(build_lps("ababd"))     # -> [0, 0, 1, 2, 0]
print(build_lps("aaaa"))      # -> [0, 1, 2, 3]

Read lps for "ababd": at the second a (index 2) the prefix "a" reappears, so lps[2] = 1; at b (index 3) the prefix "ab" reappears, so lps[3] = 2; d breaks the pattern, so lps[4] = 0. The search then uses this table to recover from mismatches without ever re-reading a text character.

def kmp_search(text, pattern):
    if not pattern:
        return 0
    lps = build_lps(pattern)
    j = 0                                   # how many pattern chars are matched so far
    for i in range(len(text)):              # i only ever moves forward
        while j > 0 and text[i] != pattern[j]:
            j = lps[j - 1]                  # reuse the border instead of restarting
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):               # matched the whole pattern
            return i - j + 1                # it started j-1 characters back
    return -1

print(kmp_search("ababcabcabababd", "ababd"))   # -> 10
print(kmp_search("aaaaab", "aab"))               # -> 3
print(kmp_search("abc", "xyz"))                  # -> -1

The outer loop index i never decreases, and each character of the text is “consumed” at most once by the j += 1 step. The inner while only ever shrinks j, and j can shrink no more times than it grew, so the total work is bounded by the length of the text.

Complexity. Building lps is O(m), and the search is O(n), for a guaranteed O(n + m) time in the worst case — no bad inputs, unlike naive search or (adversarially) Rabin–Karp. The space is O(m) for the table.

When to reach for which

• Naive search is fine when the text is short or the pattern rarely almost matches. It needs no setup and no extra memory. Python’s built-in str.find and the in operator are heavily optimized C and are the right default in real code.
• Rabin–Karp wins when you search for many same-length patterns at once, or in 2-D matching, because a hash set makes “is this window one of my patterns?” an O(1) question.
• KMP is the choice when you need a guaranteed linear worst case on a single pattern, or the text arrives as a stream you cannot rewind.

The unifying lesson is the one to carry into interviews: when a scan re-examines characters it has already seen, look for a summary — a hash, a prefix table, a counter — that lets the scan move strictly forward.

Big-O summary

Practice

1. Implement naive_search yourself and feed it text = "aaaaaaaaab", pattern = "aaaab". Add a counter for character comparisons and watch it approach n·m — that is the wasted re-reading the other algorithms avoid.

2. Build the lps table by hand for "aabaaab", then check it against build_lps. Explain in one sentence why lps[5] is 2.

3. Extend rabin_karp to return every starting index where the pattern occurs (not just the first). Test it on text = "abababab", pattern = "abab", expecting [0, 2, 4].