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

Exact substring search returns locations where a pattern matches contiguous symbols. Trying each start independently can repeat almost the same comparisons on repetitive input, costing O(nm) for text length n and pattern length m. KMP reuses matched prefixes to achieve linear preprocessing and search work.

A proper prefix is shorter than the full string. The fallback table records the longest proper prefix of each pattern prefix that is also its suffix: a border. For ababac, the table is [0, 0, 1, 2, 3, 0].

Reusing the part that already matched

While searching, j counts pattern code points matching the suffix of text already consumed. On mismatch, the previous border identifies a shorter candidate without rewinding the text cursor. For a matched ababa prefix of ababac, a following b falls back from length 5 to length 3; that same b can then extend the shorter match.

After a full match, keep the pattern's final border rather than resetting to zero. Pattern abab has border ab, so searching ababab must retain starts 0 and 2. Each fallback spends progress gained by earlier matches, which bounds total fallback work linearly.

Convert strings to code-point arrays before numeric indexing, and state that the reported positions are code-point positions. A supplementary character occupies two UTF-16 code units but one code point. Handle an empty pattern before indexing it: it matches n+1 boundaries, including the end.

const points = Array.from("A😀B");
console.log(points.length, points[1]); // 3 😀
const borders = [0, 0, 1, 2]; // for the known pattern "abab"
console.log(borders.at(-1)); // 2: retain this border after a full match

Keeping overlaps in the result

KMP's table takes O(m) time/space and search takes O(n), excluding output. Materializing code-point arrays additionally costs O(n+m) storage; do not claim only O(m) total JavaScript storage while retaining a full text array. A streaming text iterator can avoid that extra text copy. Use KMP for exact matching in repetitive text or streams; wildcards, approximate spelling and regular expressions need different state models.

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