Advanced Structures

Strings and pattern matching

KMP, Rabin-Karp, and the suffix machinery

~13 minLesson 21 of 25Written by Claude Opus 4.8

Every time you hit Ctrl-F, something scans a haystack for a needle. The obvious way - line the pattern up, compare, slide over one, repeat - is quietly quadratic. The clever way, KMP, never re-reads a character it has already matched: on a mismatch it lets the pattern jump ahead using a precomputed "failure function." This lesson builds both, side by side, and lets you step through the exact comparisons.

A string is an array - of what, exactly?

Under the hood a string is a contiguous array of small integers. The question is which integers.

ASCII - Unicode - UTF-8

ASCII is the ancestor: 7 bits, 128 slots - $A$ is 65, $a$ is 97, enough for English and punctuation. Unicode drops the 128-slot cap and assigns every character a code point (up to U+10FFFF - over a million), covering every script plus emoji. UTF-8 is how those code points become bytes: 1 byte for ASCII (so old text still works), up to 4 bytes for the rest. The catch: len() may count bytes or code units, not what a human calls "characters" - one emoji can be several code units, so string length can lie.

Immutable strings: why `a + b` in a loop bites

In most languages (Python, Java, JavaScript, C#) strings are immutable: you can't edit them in place, only build new ones. That is great for safety and sharing - but it makes naive concatenation a trap.

The accidental O(n^2)

Growing a string with s += c inside a loop looks like $O (n)$ work. It isn't. Each += must copy the entire current string into a new one, because the old string can't be mutated. Copy 1 char, then 2, then 3, ..., then $n$ :

1 + 2 + 3 + \dots + n = \frac{n ( n + 1 )}{2} = O (n^{2}) .

The fix: collect the pieces in a list / builder and join them once at the end - a single $O (n)$ pass. This is the same "amortize the copies" lesson as a growable array.

Searching: line up, compare, slide

Now the main event. Given a text of length $n$ and a pattern of length $m$ , find where the pattern occurs. The naive method aligns the pattern at position 0, compares left to right; on any mismatch it slides one step right and starts the comparison over from the pattern's first character. In the worst case (think AAAA... searched for AAAB) every one of the $n$ alignments re-compares up to $m$ characters:

T_{naive} = O (n \cdot m) .

KMP's one idea

When the naive method mismatches after matching, say, ABAB, it throws that knowledge away and restarts. But we already know those four text characters - we just read them! KMP precomputes, for each spot in the pattern, "if I fail here, how much of a matched prefix is also a suffix and can stay aligned?" That number lets the pattern jump forward while the text pointer never moves backward. Result: $O (n + m)$ .

Step through it: naive vs KMP

Type a text and a pattern (or pick a preset), then walk one comparison at a time with Next. The pattern row slides beneath the text. Flip between Naive and KMP and watch the comparison counter - and watch how, on a mismatch, KMP slides the pattern several steps at once instead of one.

Pattern-matching stepper green = match - red = mismatch

textpattern

presetsfailure fn: [0,0,1,2,0]

algorithm

text

pattern (slides right on each shift)

T[0]='A' = P[0]='A' - match. Compare the next pair.

1comparisons so far

17naive total

11kmp total

green = characters that matched - red = the mismatch - faded = text the window has passed. On a mismatch, KMP keeps the text pointer put and only slides the pattern.

The failure function (LPS)

For a pattern $P$ , define $LPS [k]$ = the length of the longest proper prefix of $P [0.. k]$ that is also a suffix of $P [0.. k]$ . For $P = ABABC$ it is $[0, 0, 1, 2, 0]$ : after matching ABAB (index 3) the prefix AB is also a suffix, so $LPS [3] = 2$ . On a mismatch at $P [j]$ , KMP sets $j \leftarrow LPS [j - 1]$ instead of $0$ - reusing that overlap so the two characters we already know match stay aligned. Building LPS is one $O (m)$ pass; the search is one $O (n)$ pass. Total $O (n + m)$ .

KMP in code

The whole search is nine lines. The single line that matters is the j = lps[j - 1] jump - that is where the text pointer i is spared from ever backing up.

def kmp_search(text, pat):
    lps = build_lps(pat)          # failure function, O(m)
    i = j = 0                    # i scans text, j scans pattern
    while i < len(text):
        if text[i] == pat[j]:
            i += 1; j += 1
            if j == len(pat):
                return i - j        # match starts here
        elif j > 0:
            j = lps[j - 1]        # JUMP: reuse matched prefix, i stays put
        else:
            i += 1               # nothing matched here, slide by one
    return -1                    # not found

Rabin-Karp: search by fingerprint

A different trick: hash the pattern once, then roll a hash over each window of the text. A rolling hash updates in $O (1)$ - drop the leaving character, add the entering one - so the whole scan is $O (n)$ on average:

h_{i + 1} = (h_{i} - t_{i} \cdot b^{m - 1}) \cdot b + t_{i + m} .

When two hashes match you still verify the characters (hashes can collide), but that is rare. Rabin-Karp shines when searching for many patterns at once, or for 2-D and plagiarism-style matching. KMP wins the single-pattern worst case; Rabin-Karp wins on flexibility.

Check yourself

Why is naive substring search O(n*m) in the worst case?

What does KMP's failure function let the search avoid?

Recall: what does KMP's failure function (LPS) store, and how does that make the pattern jump ahead?

click to reveal Try to state it, then check.

Lock it in

A string is a contiguous array of small integers; ASCII, Unicode, and UTF-8 decide which integers, and len() may count bytes or code units, not human characters.
Immutable strings make s += c in a loop $O (n^{2})$ (each += copies the whole string); collect the pieces and join once for a single $O (n)$ pass.
Naive search is $O (n \cdot m)$ because every alignment can restart from the pattern's first character; KMP never re-reads a matched text character, giving $O (n + m)$ .
KMP's failure function ( $LPS [k]$ = longest proper prefix that is also a suffix) lets the pattern jump ahead while the text pointer never backs up; Rabin-Karp instead rolls a hash and wins on multi-pattern flexibility.

Primary source

The Sedgewick & Wayne Algorithms booksite (Princeton) covers substring search and KMP with a DFA-based construction and clean, runnable Java. For a patient walkthrough of the failure function and the KMP jump, see Abdul Bari's Algorithms playlist.

Ask your teacher

Want to derive the DFA form of KMP, or see how suffix arrays and the Aho-Corasick automaton search for many patterns at once? Ask me. And this is exactly where the LLM pipeline begins: tokenization matches subword patterns in raw text, and a trie does prefix matching to route those tokens - string algorithms feeding the model before a single weight is touched.