KMP string search

You're scanning a large build log for an exact marker. Most candidate starts fail quickly, but one repetitive section almost matches the marker again and again. The simple search keeps comparing characters it has already seen.

KMP records which part of a failed match can still be useful. The payoff is predictable linear work, including when the text contains long runs of nearly matching prefixes. Built-in search remains the practical first choice when it already meets the application's needs.

Searching a repetitive build log

A failed comparison can reuse a matched prefix that is also a suffix. KMP's prefix table records the longest proper border at every pattern position; fallback decreases the matched length without rewinding the text cursor. Retaining a border after a complete match preserves overlaps.

Reusing the part that already matched

Suppose the marker is ababac and the scanner has matched ababa. The next character is b, where the marker expects c. Restarting discards useful information: the matched text already ends in aba, which is also a marker prefix. Falling back to length three lets that same b extend the retained match to abab. The text cursor doesn't move backward.

symbols := []rune("éaé")
fmt.Println(len(symbols), len("éaé")) // 3 runes, 5 bytes

Keeping overlaps in the result

Code-point indexing requires rune decoding. It does not count visible grapheme clusters. The border invariant makes repetitive inputs linear because fallback spends previously earned progress. Resetting to zero after each mismatch repeats work; resetting after a match loses overlaps. KMP suits streaming exact matching and repetitive data; wildcard and approximate matching require different state.

The fallback table costs O(m) time and space for a pattern of length m; scanning n text symbols costs O(n). Each fallback spends progress gained by earlier matches. Decoding or materializing code-point arrays can add input-sized storage, so distinguish that representation cost from the table itself.

For chunked logs, carry the current match state into the next chunk: a chunk boundary is not a mismatch.