String Matching

At a glance

The instinct

Naive matching restarts from scratch after every mismatch, which costs O(n·m) on inputs like aaaa...ab. Two ideas remove the waste:

• KMP / prefix function - after a mismatch, the part you already matched tells you how far the pattern can safely shift. pi[i] is the length of the longest border (proper prefix that is also a suffix) of s[0..i]. On a mismatch you fall back to that border instead of to zero, so the text pointer never moves backwards.
• Rolling hash (Rabin-Karp) - turn every substring into a number you can update in O(1) as a window slides, so comparing two substrings costs O(1) instead of O(length). Hashes can collide, so use two moduli or verify matches.

Recognise it

Not this pattern if...

• Characters may be rearranged (anagram search) - that is a sliding window with counts.
• You match many patterns against one text or need prefix queries - a trie (or Aho-Corasick) fits better.
• Wildcards like ? and * are involved - that is string DP.

Memory hack

Analogy: KMP is a musician who loses their place in a song and restarts at the last chorus they know is identical - not at the very beginning. A rolling hash is a cashier sliding a window over a receipt: add the new item, subtract the one that fell out, and the running total updates instantly.

Say it out loud in the interview:

1. "Naive search is O(n·m); I can make it linear because the matched part already tells me where to resume."
2. "I'll build the prefix function of the pattern (or the combined string pattern + '#' + text)."
3. "If I need many substring comparisons, I'll precompute prefix hashes with two moduli and compare in O(1)."

How it works

The prefix function grows by at most one per character and can only shrink as much as it grew, so the inner while loop runs O(n) times in total. Trace for s = "ababcabab":

So the longest proper prefix of the whole string that is also its suffix is "abab" (length 4). For Shortest Palindrome, run this on s + "#" + reverse(s): the final value is the length of the longest palindromic prefix of s, and you prepend the reverse of the remainder. The # stops a border from spilling across both halves.

Java template

import java.util.*;

class StringMatching {
    // pi[i] = length of the longest proper prefix of s[0..i] that is also a suffix of it.
    static int[] prefixFunction(String s) {
        int n = s.length();
        int[] pi = new int[n];
        for (int i = 1; i < n; i++) {
            int k = pi[i - 1];
            while (k > 0 && s.charAt(i) != s.charAt(k)) k = pi[k - 1];  // fall back to a shorter border
            if (s.charAt(i) == s.charAt(k)) k++;
            pi[i] = k;
        }
        return pi;
    }

    // All start indices of pat in text, O(n + m). Assumes pat is non-empty.
    static List<Integer> kmpSearch(String text, String pat) {
        int[] pi = prefixFunction(pat);
        List<Integer> hits = new ArrayList<>();
        int k = 0;                                              // chars of pat matched so far
        for (int i = 0; i < text.length(); i++) {
            while (k > 0 && text.charAt(i) != pat.charAt(k)) k = pi[k - 1];
            if (text.charAt(i) == pat.charAt(k)) k++;
            if (k == pat.length()) {
                hits.add(i - k + 1);
                k = pi[k - 1];                                  // keep going for overlapping hits
            }
        }
        return hits;
    }
}

class RollingHash {
    private static final long M1 = 1_000_000_007L, M2 = 998_244_353L, BASE = 131;
    private final long[] h1, h2, p1, p2;

    RollingHash(String s) {
        int n = s.length();
        h1 = new long[n + 1]; h2 = new long[n + 1];
        p1 = new long[n + 1]; p2 = new long[n + 1];
        p1[0] = p2[0] = 1;
        for (int i = 0; i < n; i++) {
            h1[i + 1] = (h1[i] * BASE + s.charAt(i)) % M1;
            h2[i + 1] = (h2[i] * BASE + s.charAt(i)) % M2;
            p1[i + 1] = p1[i] * BASE % M1;
            p2[i + 1] = p2[i] * BASE % M2;
        }
    }

    // Fingerprint of s[l, r): two hashes packed into one long (both are < 2^30).
    long get(int l, int r) {
        long a = (h1[r] - h1[l] * p1[r - l] % M1 + M1) % M1;
        long b = (h2[r] - h2[l] * p2[r - l] % M2 + M2) % M2;
        return (a << 32) | b;
    }

    // Typical use: does some substring of length len occur twice? (binary search on len outside)
    int repeatedStart(int n, int len) {
        Set<Long> seen = new HashSet<>();
        for (int i = 0; i + len <= n; i++) {
            if (!seen.add(get(i, i + len))) return i;
        }
        return -1;
    }
}

Complexity

Variations

• Single-pattern search - KMP, Z-function or Rabin-Karp. Find the Index of the First Occurrence in a String, Repeated String Match.
• Borders and periods - last pi value gives the longest border; n - pi[n-1] gives the smallest period. Longest Happy Prefix, Repeated Substring Pattern.
• Palindromic prefix via a mirror - prefix function of s + '#' + reverse(s). Shortest Palindrome.
• Hash + binary search on length - "a repeat of length L exists" is monotonic in L. Longest Duplicate Substring, Longest Common Subpath.
• Z-function - z[i] = longest match between the string and its suffix at i; same problems, sometimes simpler to reason about. Sum of Scores of Built Strings.
• Many patterns at once - trie of patterns with failure links (Aho-Corasick), the multi-pattern generalisation of KMP.

Common mistakes

• Resetting k to 0 after a full match - you miss overlapping occurrences; use k = pi[k - 1].
• Forgetting + M after subtracting in the hash formula, so Java's % returns a negative fingerprint.
• Calling substring() or String.hashCode() inside a sliding loop - each call is O(length), quietly making it O(n·m) again.
• Building the combined string without a separator that cannot appear in the input, letting borders cross the boundary.
• In Repeated String Match, stopping at exactly ceil(len b / len a) copies - one extra copy is needed when b starts mid-way through a.

All practice problems

3 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.