String Matching — KMP & Rabin-Karp¶

Illustrative interview

A long prefix matches, the next character fails, and the naive matcher restarts from scratch. The discarded prefix already contains information about the next viable alignment. KMP records that information so the text pointer never moves backward.

Difficulty: Hard | Pattern Type: Substring search

← DSA Overview | ← Greedy Algorithms | Next: Advanced String Matching →

Multi-pattern matching and beyond

This page covers single-pattern KMP and Rabin-Karp. For multi-pattern matching (Aho-Corasick), the Z-algorithm, suffix arrays, Boyer-Moore, and Manacher's algorithm, see Advanced String Matching.

Why These Algorithms Exist¶

The naive way to find a pattern of length m inside a text of length n checks every starting position and compares character by character: O(nm) worst case. For text search at scale (log scanning, DNA sequence matching, plagiarism detection), that's too slow.

KMP (Knuth-Morris-Pratt) and Rabin-Karp both achieve better-than-naive matching, but via completely different mechanisms:

KMP never re-examines a text character it has already matched — it uses information about the pattern's own internal structure to skip redundant comparisons.
Rabin-Karp uses a rolling hash to compare whole substrings in O(1) amortized per position, only falling back to character comparison on a hash collision.

Mental Model¶

Pattern ababd mismatches text ababc on the last character. The border of the matched abab is ab, and the text pointer stays put.

KMP's insight: when a mismatch occurs after matching some prefix of the pattern, you already know exactly what the last few text characters were — they equal the pattern's prefix up to the mismatch. If that prefix has a shorter substring that is both a prefix and a suffix of itself, you can resume matching from there instead of restarting the pattern at position 0 and re-scanning text you already saw.

Text:     a  b  a  b  c  a  b  a  b  a  b  d
Pattern:  a  b  a  b  d
                    ^ mismatch: text 'c' vs pattern 'd'  (not 'a')
                      "abab" already matched

LPS table for "ababd": [0,0,1,2,0]
  lps[3] = 2 means "ab" is both a prefix and suffix of "abab"

On mismatch at j=4, set j = lps[3] = 2; leave the text pointer i on 'c'.
Next comparison is text 'c' vs pattern[2]='a' — still a mismatch, so fall
back again (j = lps[1] = 0) and then advance i. The TEXT pointer never
moves backward. That's the O(n) guarantee.

The interactive visualizer uses a longer string (ababcabcabababd) with the same pattern ababd; the first mismatch is still 'c' vs 'd' after matching "abab".

Rabin-Karp's insight: compute a hash of the pattern once, then slide a window across the text computing each window's hash incrementally (O(1) per shift via a rolling hash formula), and only do a full character comparison when hashes collide — hash equality is necessary but not sufficient for a real match.

Interactive Pattern Matching Visualizer¶

🔎 KMP: Pattern Matching with the Failure Function

Unmatched Text pointer (i) Pattern pointer (j) Confirmed match

Watch the pattern row shift right on a mismatch, using the LPS table instead of restarting from scratch — the top (text) row's pointer never moves backward.

Implementation¶

KMP¶

def compute_lps(pattern: str) -> list[int]:
    """Longest Proper Prefix that's also a Suffix, for every prefix of pattern.
    lps[i] = length of the longest string that is both a prefix and suffix of pattern[:i+1]."""
    lps = [0] * len(pattern)
    length = 0  # length of the previous longest prefix-suffix
    i = 1

    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length > 0:
            length = lps[length - 1]  # fall back within the pattern, don't reset to 0
        else:
            lps[i] = 0
            i += 1

    return lps
    # Time: O(m) where m = len(pattern)


def kmp_search(text: str, pattern: str) -> list[int]:
    """Returns all starting indices where pattern occurs in text."""
    if not pattern:
        return []

    lps = compute_lps(pattern)
    matches = []
    i = j = 0  # i: text pointer, j: pattern pointer

    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == len(pattern):
                matches.append(i - j)
                j = lps[j - 1]  # continue searching for overlapping matches
        elif j > 0:
            j = lps[j - 1]  # fall back using the failure function — i never moves backward
        else:
            i += 1

    return matches
    # Time: O(n + m) — i only ever increases; total pattern-pointer decreases are bounded by
    #        total increases, so the amortized work is linear
    # Space: O(m) for the LPS table

Rabin-Karp¶

def rabin_karp_search(text: str, pattern: str, base: int = 256, mod: int = 10**9 + 7) -> list[int]:
    """Rolling hash — compare hashes first, fall back to full comparison on collision."""
    n, m = len(text), len(pattern)
    if m > n or m == 0:
        return []

    high_order = pow(base, m - 1, mod)  # base^(m-1) mod p, for removing the leading digit
    pattern_hash = 0
    window_hash = 0
    for i in range(m):
        pattern_hash = (pattern_hash * base + ord(pattern[i])) % mod
        window_hash = (window_hash * base + ord(text[i])) % mod

    matches = []
    for i in range(n - m + 1):
        if pattern_hash == window_hash:
            if text[i:i + m] == pattern:  # verify — hash collisions are possible
                matches.append(i)

        if i < n - m:
            # Roll the window: remove text[i]'s contribution, shift, add text[i+m]
            window_hash = (window_hash - ord(text[i]) * high_order) % mod
            window_hash = (window_hash * base + ord(text[i + m])) % mod
            window_hash %= mod  # normalize in case of negative modulo

    return matches
    # Time: O(n + m) average (O(1) amortized per shift); O(nm) worst case under
    #        adversarial input that causes many hash collisions
    # Space: O(1) extra beyond the output list

Rabin-Karp's worst case is not guaranteed linear

A poorly chosen modulus (or an adversary who knows it) can force many spurious hash collisions, degrading to O(nm) — every window triggers a full O(m) verification. KMP has a hard O(n+m) guarantee regardless of input; Rabin-Karp trades that guarantee for simplicity and for being trivially extensible to multi-pattern search (hash all patterns, check every window's hash against the set).

When to Use Which¶

Scenario	Algorithm	Why
Single pattern, need a hard worst-case guarantee	KMP	O(n+m) always, no adversarial degradation
Searching for many patterns at once	Rabin-Karp (or Aho-Corasick for true multi-pattern)	Hash set of pattern hashes makes multi-pattern nearly free per position
2D pattern matching (e.g., substring in a grid)	Rabin-Karp	Rolling hash generalizes to 2D more naturally than KMP's linear failure function
Plagiarism / duplicate detection across huge corpora	Rabin-Karp (or its cousin, Rabin fingerprinting for chunking)	Hash-based comparison scales to comparing many documents pairwise
Simplicity matters more than worst-case guarantee	Rabin-Karp	Conceptually simpler to implement correctly than the LPS table
Streaming text, can't re-scan	KMP	Never needs to look backward in the text — genuinely one-pass
Built-in language function is available	Use it (`str.find`, `in`)	Production string search in most languages is already highly optimized (often Boyer-Moore or a hybrid) — implement KMP/Rabin-Karp for interviews, not for a real substring search in application code

Common Problems and Patterns¶

Find the Index of the First Occurrence (strStr)¶

def str_str(haystack: str, needle: str) -> int:
    """Classic KMP application — the canonical 'implement strstr' interview question."""
    if not needle:
        return 0
    matches = kmp_search(haystack, needle)
    return matches[0] if matches else -1
    # Time: O(n + m)

Repeated Substring Pattern (KMP's LPS Table, Repurposed)¶

def repeated_substring_pattern(s: str) -> bool:
    """s is built by repeating a substring iff len(s) is divisible by
    (len(s) - lps[-1]), the length of the smallest repeating unit."""
    lps = compute_lps(s)
    n = len(s)
    period = n - lps[-1]
    return period != n and n % period == 0
    # Time: O(n) — reuses the LPS computation directly, no extra search needed

Longest Duplicate Substring (Rabin-Karp + Binary Search)¶

def longest_dup_substring(s: str) -> str:
    """Binary search on answer length; for each length, use rolling hashes to
    check in O(n) whether any substring of that length repeats."""
    def search(length: int) -> int:
        if length == 0:
            return -1
        base, mod = 26, 2**63 - 1
        h = 0
        for i in range(length):
            h = (h * base + (ord(s[i]) - 97)) % mod
        seen = {h: [0]}
        high_order = pow(base, length - 1, mod)

        for start in range(1, len(s) - length + 1):
            h = (h - (ord(s[start - 1]) - 97) * high_order) % mod
            h = (h * base + (ord(s[start + length - 1]) - 97)) % mod
            h %= mod
            if h in seen:
                for prev_start in seen[h]:
                    if s[prev_start:prev_start + length] == s[start:start + length]:
                        return start
                seen[h].append(start)
            else:
                seen[h] = [start]
        return -1

    lo, hi, result = 1, len(s) - 1, ""
    while lo <= hi:
        mid = (lo + hi) // 2
        start = search(mid)
        if start != -1:
            result = s[start:start + mid]
            lo = mid + 1  # try to find a longer duplicate
        else:
            hi = mid - 1
    return result
    # Time: O(n log n) average — binary search over length × O(n) rolling-hash check per length

Complexity Summary¶

Algorithm	Time (average)	Time (worst case)	Space	Guarantee
Naive search	O(nm)	O(nm)	O(1)	None
KMP	O(n + m)	O(n + m)	O(m) for LPS table	Hard guarantee, no degradation
Rabin-Karp	O(n + m)	O(nm)	O(1) extra	Probabilistic — degrades on hash collisions
Aho-Corasick (multi-pattern)	O(n + Σm + z)	Same	O(Σm)	z = number of matches; extends KMP's failure function to a trie

n = text length, m = pattern length.

Interview Follow-ups¶

"Why doesn't KMP's text pointer ever move backward?" — The failure function encodes exactly how much of the already-matched text can be reused as the start of a new match attempt — that's the entire point of building the LPS table.
"How would you extend Rabin-Karp to search for multiple patterns simultaneously?" — Hash all patterns into a set upfront; for each text window, compute its rolling hash and check set membership — O(1) average per window regardless of pattern count, versus O(k(n+m)) for k separate KMP passes.
"What breaks Rabin-Karp in an adversarial setting?" — An attacker who knows your modulus can craft many strings that collide under your hash, forcing O(m) verification at every position — use a large random modulus, or a cryptographic hash if adversarial input is a real threat.
"KMP vs Z-function — what's the difference?" — The Z-function computes, for every position, the length of the longest substring starting there that matches the text's prefix — a different but related preprocessing tool; both solve pattern matching in O(n+m), and the Z-function is often considered more intuitive to derive from scratch.

Key Takeaways¶

Remember

KMP precomputes the pattern's LPS (failure function) table so the text pointer never moves backward — hard O(n+m) guarantee.
Rabin-Karp uses a rolling hash for O(1) amortized comparison per position, falling back to full comparison on collision — O(n+m) average, O(nm) worst case.
KMP wins when you need a guarantee; Rabin-Karp wins when you need simplicity or multi-pattern search.
The LPS table answers: "if I mismatch here, how much of what I already matched can I reuse?" — that's the entire mechanism.
In real production code, use the language's built-in substring search — implement these from scratch for interviews and for genuinely specialized cases (streaming, multi-pattern, adversarial-input hardening).