String Matching (KMP)

String matching asks a simple question: does a small pattern appear inside a bigger text, and where? The obvious way is to slide the pattern along and re-check from scratch at every position — but that throws away work and runs in O(n·m). KMP (Knuth–Morris–Pratt) is the classic fix: it never re-scans a character of the text, finishing in O(n + m).

Intuition

Imagine checking whether a long sentence contains the word "ABAB". The naive reader, on hitting a wrong letter, walks all the way back and tries again one space over. KMP is the reader who remembers: "I just matched ABA before the mismatch, and ABA ends in A — which is also how my pattern starts. So I do not need to recheck that leading A; I can keep it and resume." The LPS table is that memory, computed once from the pattern alone.

The naive scan is O(n·m) because each of the n starting positions can re-compare up to m characters. KMP spends a one-time O(m) building the LPS, then sweeps the text in a single O(n) pass. The text pointer i only ever moves forward — that is the whole win.

Walk through it

On the right, the text ABABCABAB is the top row and the pattern ABAB is the row that slides underneath. Pointer i scans the text; pointer j scans the pattern. Matching characters light up, and matched-so-far cells stay shaded so you can see how much progress carries over.

Watch the key moment. After matching ABAB at index 0, the next text character is C, which does not match. Instead of dragging the pattern back to the start, KMP reads lps[j-1] and slides the pattern forward by the smart amount, keeping the prefix it already knows. A few steps later it locks onto the second ABAB at index 5 — having touched every text character exactly once.

The code, line by line

def compute_lps(pat):
    lps = [0] * len(pat)
    length = 0          # length of the current longest prefix-suffix
    i = 1
    while i < len(pat):
        if pat[i] == pat[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length > 0:
            length = lps[length - 1]   # fall back, don't reset
        else:
            lps[i] = 0
            i += 1
    return lps
 
def kmp_search(text, pat):
    lps = compute_lps(pat)
    i = j = 0                          # i over text, j over pattern
    matches = []
    while i < len(text):
        if text[i] == pat[j]:
            i += 1
            j += 1
            if j == len(pat):
                matches.append(i - j)  # found a full match
                j = lps[j - 1]         # resume without rescanning
        elif j > 0:
            j = lps[j - 1]             # slide pattern by the smart amount
        else:
            i += 1                     # j already 0: just move on
    return matches

• compute_lps builds the table in O(m). For "ABAB" it returns [0, 0, 1, 2]: at index 3, the longest prefix (AB) that is also a suffix has length 2.
• Line 18 runs that one-time preprocessing before the search even starts.
• Line 22 is the character comparison. On a match we advance both cursors (lines 23–24); a full pattern (j == len(pat)) records a hit at i - j.
• Line 28–29 are the heart of KMP: on a mismatch with j > 0, we set j = lps[j-1]. That keeps i fixed and reuses the matched prefix — the "slide" you see in the animation.
• The else branch (j == 0) means nothing matched yet, so we just step i forward.

Complexity

The extra space is the LPS table, one slot per pattern character. The search itself is linear because the text pointer i only moves forward and j is bounded — amortized, each text character is compared a constant number of times.

Rabin–Karp, in one breath

A different linear-on-average approach is Rabin–Karp: hash the pattern, then roll a hash across every length-m window of the text. A rolling hash updates in O(1) per shift — subtract the outgoing character, add the incoming one — so you compare a cheap integer instead of m characters. When hashes match, verify the actual substring to rule out a hash collision. Average O(n + m); worst case O(n·m) if collisions pile up. It shines when searching for many patterns at once (hash them all into a set).

When to use / pitfalls

Practice