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

Find every pattern start, including overlaps, without repeatedly rescanning a long matched prefix. String positions in this exercise are code-point indices, which can differ from Java char offsets.

A direct search tries each start independently and can compare the same prefix many times. KMP stores fallback information for matched prefixes. Resetting the matched length to zero after a match loses useful overlap information.

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.

When a comparison fails, KMP retains the longest proper prefix that is also a suffix of the matched prefix. Falling back through prefix links never moves the text cursor backwards. After a complete match, fall back rather than reset to retain overlaps. Final target O(n+m) time, O(m) workspace.

A proper prefix can also be a suffix of the pattern. That overlap is the state worth retaining after a complete match:

import java.util.*;

class Example {
    public static void main(String[] args) {
        String pattern = "aba";
        String properPrefix = pattern.substring(0, 1);
        String properSuffix = pattern.substring(pattern.length() - 1);
        assert properPrefix.equals(properSuffix);
        assert "ababa".startsWith(pattern, 0);
        assert "ababa".startsWith(pattern, 2);
    }
}

The suffix a can be the beginning of a new match, so completing aba does not discard it. A prefix table generalizes this observation to every matched length. The snippet demonstrates overlap only; it does not build that table or search arbitrary inputs.

Keeping overlaps in the result

Prefix fallback is useful in streaming text matching and repeated delimiter detection, where preserving already-established comparisons avoids quadratic behavior on repetitive input.

Return all ascending match starts measured in Unicode code points, not UTF-16 char offsets. Compare exactly, preserving case and normalization form. An empty pattern matches every code-point boundary, including the end. ("ababa","aba") gives [0,2].

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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