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 mismatch after a long prefix need not restart comparison at the next text position. KMP stores each prefix's longest proper border: a prefix that is also a suffix. For ababac, the border lengths are 0,0,1,2,3,0. On the final mismatch, the candidate border falls from 3 to 1 to 0 without moving the text cursor backward.

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.

Text pattern=U"abab";
std::vector<Int> borders{0,0,1,2};
// A full match falls back to borders.back()==2, retaining overlapping matches.

Keeping overlaps in the result

Resetting to zero after a match would miss the second occurrence in ababab. Each fallback spends progress gained by prior matches, yielding O(n+m) total work. Code-point indices are distinct from UTF-8 byte positions and from visible grapheme positions; Text makes the selected unit explicit. Handle the empty pattern before indexing it: it matches all n+1 boundaries. A naive character-by-character search is a useful prototype because its independent comparison structure makes overlap behavior easy to review.

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.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged. Text ordering follows Unicode code points (Text) or the documented UTF-8 identifier order (std::string).

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