String Matching with KMP

Searching a text of length $n$ for a pattern of length $m$ with the obvious nested loop — try every starting position, compare character by character — costs $O(nm)$ in the worst case, because a near-match that fails on the last character forces you to slide over by one and re-check almost everything again. Knuth-Morris-Pratt (KMP) does the same search in $O(n + m)$ by never re-examining a text character once it has been matched, using a table built once from the pattern alone.

The idea: the pattern tells you how far you can safely skip

The key insight: when a match fails partway through, you already know something about the text you just scanned — it equals a prefix of the pattern. If that already-scanned chunk happens to also end in a shorter prefix of the pattern, you can resume comparing from after that shorter prefix instead of restarting from scratch, because you know those characters would match anyway.

This is captured in the failure function (also called the LPS, longest proper prefix that is also a suffix, array): lps[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix of pattern[0..i]. Building this table takes $O(m)$ using the pattern against itself. Then scanning the text takes $O(n)$: on a mismatch at pattern position $j$, jump to lps[j-1] instead of restarting $j$ at 0, and — critically — never move the text pointer backward. Each text character is compared a bounded number of times, giving the linear total.

Worked example: match "ABABC" in text "ABABABC"

LPS for "ABABC": index 0 A→0 (single char, no proper prefix); index 1 AB→0 (no matching prefix/suffix); index 2 ABA→1 (A is both prefix and suffix); index 3 ABAB→2 (AB is both); index 4 ABABC→0 (C breaks the pattern). So lps = [0,0,1,2,0].

Scanning text "ABABABC": positions 0-3 match A,B,A,B against pattern's A,B,A,B. At text index 4, pattern index 4 expects C but text has A — mismatch. Instead of restarting the pattern pointer at 0 and retreating the text pointer, jump the pattern pointer to lps[3] = 2 (keep the text pointer at index 4). Now compare pattern index 2 (A) against text index 4 (A) — match; pattern index 3 (B) against text index 5 (B) — match; pattern index 4 (C) against text index 6 (C) — match. Full pattern matched, ending at text index 6. Total text characters examined: 7, each visited once or twice, never re-scanned from the start.

def build_lps(pattern):                 # O(m)
    lps = [0] * len(pattern)
    length = 0
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length:
            length = lps[length - 1]    # fall back, don't advance i
        else:
            lps[i] = 0
            i += 1
    return lps

def kmp_search(text, pattern):          # O(n + m)
    lps = build_lps(pattern)
    i = j = 0
    matches = []
    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]
        elif j:
            j = lps[j - 1]
        else:
            i += 1
    return matches

Where it shows up

Interview framing: "implement strStr()" (LeetCode 28) is the textbook ask, plus "shortest palindrome" and repeated-substring-pattern problems that lean on the LPS array in clever ways. On a desk, exact pattern search over log files or tick data streams, and detecting repeated structural motifs in symbolic sequences (order-flow patterns, message templates), benefit from KMP's guarantee of linear time with no pathological worst case, unlike naive matching on adversarial or highly repetitive input.