String Matching

Why not the obvious approach

Comparing the pattern against every starting position costs O(NM) — for a text of 10⁶ and a pattern of 10³, that is 10⁹ character comparisons. Java’s String.indexOf uses roughly this approach and is fast enough surprisingly often, but it degrades on adversarial input such as a text of all a and a pattern of aaa...ab.

The techniques below are O(N + M) and predictable.

The prefix function

For each position in a string, record the length of the longest proper prefix that is also a suffix ending there. This table is what lets a matcher skip forward without re-examining characters.

static int[] prefixFunction(String s) {
    int n = s.length();
    int[] pi = new int[n];

    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s.charAt(i) != s.charAt(j)) {
            j = pi[j - 1];                 // fall back to the next shorter candidate
        }
        if (s.charAt(i) == s.charAt(j)) j++;
        pi[i] = j;
    }
    return pi;
}

For "ababa" the table is [0, 0, 1, 2, 3]: at the last position, "aba" is both a prefix and a suffix.

The while loop looks like it could be expensive, but j only ever decreases inside it and increases at most once per outer iteration, so the total work is O(N).

KMP search

Concatenate the pattern, a separator that appears in neither string, and the text. Any position where the prefix function equals the pattern length marks a match.

static List<Integer> findAll(String text, String pattern) {
    String combined = pattern + '\1' + text;
    int[] pi = prefixFunction(combined);
    int m = pattern.length();

    List<Integer> matches = new ArrayList<>();
    for (int i = m + 1; i < combined.length(); i++) {
        if (pi[i] == m) {
            matches.add(i - 2 * m);        // start index in the original text
        }
    }
    return matches;
}

The separator is essential. Without it, a prefix-function value could span the boundary and report a match that does not exist. Pick a character guaranteed absent — '\1' works when the input is printable text.

The Z-function

A close relative: z[i] is the length of the longest substring starting at i that matches a prefix of the whole string. Some problems are cleaner with this formulation.

static int[] zFunction(String s) {
    int n = s.length();
    int[] z = new int[n];
    int l = 0, r = 0;                      // the rightmost matching window

    for (int i = 1; i < n; i++) {
        if (i < r) {
            z[i] = Math.min(r - i, z[i - l]);   // reuse what the window already proved
        }
        while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) {
            z[i]++;
        }
        if (i + z[i] > r) { l = i; r = i + z[i]; }
    }
    return z;
}

The [l, r) window records the match that extends furthest right. Inside it, previously computed values transfer directly, which is what keeps the total linear.

Rolling hashes

KMP finds one pattern. When you need to compare arbitrary substrings of a string against each other, hashing is the tool. Precompute prefix hashes and any substring’s hash becomes O(1).

static final long MOD = 1_000_000_007L;
static final long BASE = 131;

static long[] hash, power;

static void build(String s) {
    int n = s.length();
    hash = new long[n + 1];
    power = new long[n + 1];
    power[0] = 1;

    for (int i = 0; i < n; i++) {
        hash[i + 1] = (hash[i] * BASE + s.charAt(i)) % MOD;
        power[i + 1] = power[i] * BASE % MOD;
    }
}

// hash of s[l..r), 0-based half-open
static long substringHash(int l, int r) {
    long h = (hash[r] - hash[l] * power[r - l]) % MOD;
    return (h + MOD) % MOD;                // normalize a possible negative
}

Two substrings of equal length are almost certainly equal when their hashes match. The normalization on the last line is required — the subtraction can go negative, and skipping it gives wrong comparisons. See Modular Arithmetic.

Choosing

Which string technique

Java-specific notes

charAt on a String is a bounds-checked method call. In a hot loop over 10⁶ characters, converting to a char[] once is noticeably faster:

char[] c = s.toCharArray();

Also avoid building strings with + inside a loop — each concatenation copies the whole thing, making an O(N) loop O(N²). Use StringBuilder.

Related