Java KMP substring search: reused prefix information and UTF-16 indices

Java 8+. This is a complete program using JDK classes.

Keep the meaning of each index

The prefix value at position i records the length of a proper pattern prefix that is also a suffix ending at i. On a mismatch, that value tells the search how much of its matched pattern can still be useful.

The text index never moves backward. The pattern index may fall back several times, but each successful advance creates only a bounded amount of later fallback work. That accounting gives the combined linear bound rather than merely hoping that typical inputs have few repeated prefixes.

This implementation compares Java char values and returns a UTF-16 index like ordinary String indexing. It does not normalize text or treat user-perceived characters as matching units. The empty pattern returns zero by the method contract; an absent nonempty pattern returns minus one.

Working program

public class ManifestPatternSearch {
    static int[] prefixes(String pattern) {
        int[] fallback = new int[pattern.length()]; int matched=0;
        for (int i=1; i<pattern.length(); i++) {
            while (matched>0 && pattern.charAt(i)!=pattern.charAt(matched)) matched=fallback[matched-1];
            if (pattern.charAt(i)==pattern.charAt(matched)) matched++;
            fallback[i]=matched;
        }
        return fallback;
    }
    static int find(String text, String pattern) {
        java.util.Objects.requireNonNull(text); java.util.Objects.requireNonNull(pattern);
        if (pattern.isEmpty()) return 0;
        int[] fallback=prefixes(pattern); int matched=0;
        for (int i=0; i<text.length(); i++) {
            while (matched>0 && text.charAt(i)!=pattern.charAt(matched)) matched=fallback[matched-1];
            if (text.charAt(i)==pattern.charAt(matched)) matched++;
            if (matched==pattern.length()) return i-pattern.length()+1;
        }
        return -1;
    }
    public static void main(String[] args) {
        System.out.println(find("PKPKPKOK", "PKOK"));
        System.out.println(find("dispatch", "lost"));
        System.out.println(find("dispatch", ""));
    }
}

Output

4
-1
0

Costs and boundaries

For text length n and pattern length m, preprocessing and search use O(n+m) comparisons and O(m) auxiliary storage. Null inputs are not accepted; the implementation will fail rather than interpret null as an empty string. Repeated searches for one pattern can reuse its preprocessed state in a separate immutable matcher.

Common Mistakes

• The prefix must be proper; the whole prefix is not its own fallback.
• A returned index is measured in UTF-16 units.
• Resetting to zero on every mismatch loses the fallback information.

Read next

Text equality policy, Pattern grammar matching.

Extend the tested workflow

Continue with Java Z algorithm: find overlapping pattern matches in linear time.