templates · Bits, range queries & string matching

KMP (prefix function)

  • Find a pattern inside a text in O(n + m), with no hashing and no bad worst case
  • "Longest prefix that is also a suffix" (a happy prefix, a border)
  • Is a string made of one repeated block? Shortest palindrome by adding letters in front?

KMP / prefix function

the one rule

The invariant

After step i, matched is the length of the longest prefix of the pattern that ends exactly at text position i.

write it from memory

The template

prefix function (lps)

javajava.util.*
/** lps[i] = length of the longest proper prefix of p[0..i] that is also a suffix of it. */static int[] prefixFunction(String p) {    int[] lps = new int[p.length()];                     // lps[0] = 0: a proper prefix is shorter    int len = 0;                                         // current matched prefix length    for (int i = 1; i < p.length(); i++) {        while (len > 0 && p.charAt(i) != p.charAt(len)) {            len = lps[len - 1];                          // fall back to a shorter border        }        if (p.charAt(i) == p.charAt(len)) len++;        lps[i] = len;    }    return lps;}

The pattern is matched against itself. On a mismatch, fall back to the next shorter border instead of starting over.

fill in the blanks — only these lines change per problem

  1. line 3Often the answer is read straight from lps, e.g. lps[n - 1] is the longest happy prefix.

search in a text

javajava.util.*
/** Every index where `pattern` starts in `text`, in O(n + m). */static List<Integer> findAll(String text, String pattern) {    List<Integer> starts = new ArrayList<>();    int m = pattern.length();    if (m == 0) return starts;                           // decide what an empty pattern means    int[] lps = prefixFunction(pattern);    int matched = 0;                                     // characters of pattern matched so far    for (int i = 0; i < text.length(); i++) {        while (matched > 0 && text.charAt(i) != pattern.charAt(matched)) {            matched = lps[matched - 1];                  // never move i back        }        if (text.charAt(i) == pattern.charAt(matched)) matched++;        if (matched == m) {                              // full match ends at i            starts.add(i - m + 1);            matched = lps[m - 1];                        // keep going: matches may overlap        }    }    return starts;}

The same loop as prefixFunction, now walking the text. Like Ctrl+F that never re-reads a character.

fill in the blanks — only these lines change per problem

  1. line 5What an empty pattern returns: Java's indexOf("") gives index 0, a "find all" may want an empty list. (LeetCode 28 now promises a non-empty pattern.)
  2. line 13What to do with a match: record the start, count it, or return at the first one.
  3. line 15After a match, lps[m - 1] allows overlapping matches; set matched = 0 to forbid them.

complexity

What it costs

time O(n + m)
i never moves back. matched goes up by at most 1 per character, so all the fallbacks together are at most n steps. Building lps is the same argument on the pattern: O(m).
space O(m)
Only the lps array for the pattern.

watch out

Common bugs

  • Using if instead of while for the fallback. One step back may not be enough.
  • Falling back to lps[len] instead of lps[len - 1].
  • Moving i backwards after a mismatch. That turns it back into the O(n × m) brute force.

use it

Practise it on

learn it properly