KMP Algo

The problem, simply

You get a long text of length n and a short pattern of length m. Give back every index in the text where the pattern starts. Matches may overlap.

The famous fast way is called KMP, after the three people who found it: Knuth, Morris and Pratt.

A story to remember it

Picture it

Examples

Way 1: the simple way

Put the pattern under the text at every start position and compare letter by letter. On the first mismatch, slide the pattern one step right and compare from its first letter again.

1. For each start s from 0 to n - m.
2. Compare text[s + k] with pattern[k] for k = 0, 1, ....
3. If all m letters match, write down s.

import java.util.*;

class Solution {
    public List<Integer> search(String text, String pattern) {
        List<Integer> found = new ArrayList<>();
        int n = text.length(), m = pattern.length();
        if (m == 0) return found;
        for (int s = 0; s + m <= n; s++) {
            int k = 0;
            while (k < m && text.charAt(s + k) == pattern.charAt(k)) k++;
            if (k == m) found.add(s);           // every letter matched
        }
        return found;
    }
}

How long it takes: each of about n starts can compare up to m letters, for example text AAAA...AB and pattern AAAB. So O(n * m). Extra room: O(1).

Way 2: the clever way

The slow part of Way 1 is forgetting. After matching ABAB, it moves on and checks the same letters again. KMP builds a cheat sheet first, called the lps table (longest proper prefix that is also a suffix).

lps[i] answers: in pattern[0..i], what is the longest start that is also an end, not counting the whole piece? For ABAB that is AB, so lps[3] = 2.

Then search with two fingers: i on the text, which only moves forward, and j on the pattern, which counts how many letters match right now.

1. If text[i] matches pattern[j], move both forward.
2. If it does not match and j > 0, set j = lps[j - 1] and try the same text[i] again.
3. If it does not match and j is 0, move i forward.
4. If j reaches m, record a match at i - m + 1, then set j = lps[m - 1] to keep looking.

The cheat sheet is built the same way, by matching the pattern against itself.

import java.util.*;

class Solution {
    // lps[i] = length of the longest start of pattern[0..i] that is also its end
    int[] buildLps(String p) {
        int m = p.length();
        int[] lps = new int[m];
        int len = 0;
        for (int i = 1; i < m; i++) {
            while (len > 0 && p.charAt(i) != p.charAt(len)) {
                len = lps[len - 1];            // fall back, do not restart
            }
            if (p.charAt(i) == p.charAt(len)) len++;
            lps[i] = len;
        }
        return lps;
    }

    public List<Integer> search(String text, String pattern) {
        List<Integer> found = new ArrayList<>();
        int n = text.length(), m = pattern.length();
        if (m == 0) return found;
        int[] lps = buildLps(pattern);
        int j = 0;                              // letters matched right now
        for (int i = 0; i < n; i++) {           // i never goes back
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = lps[j - 1];
            }
            if (text.charAt(i) == pattern.charAt(j)) j++;
            if (j == m) {
                found.add(i - m + 1);
                j = lps[m - 1];                 // keep going, matches may overlap
            }
        }
        return found;
    }
}

How long it takes: i moves forward n times. j goes up by at most 1 per step, and every fall back makes it smaller, so all the fall backs together are at most n. Building the table is the same story with m. Total O(n + m). Extra room: the lps table, O(m).

Watch out for

• After a full match, set j = lps[m - 1], not j = 0, or overlapping matches like AA in AAAA are missed.
• lps[0] is always 0. The loop that builds the table starts at i = 1.
• The "proper" in the name matters: the whole word does not count as its own start and end.
• An empty pattern needs a rule. Here it returns an empty list. Ask the interviewer.

What interviewers ask next

• Does a string repeat a smaller block, like abcabc? Build lps for it. If L = lps[n - 1] is above 0 and n % (n - L) == 0, yes.
• Shortest palindrome by adding letters at the front? Build lps of s + "#" + reverse(s). The last value is the longest palindrome start.
• Is b a rotation of a? Same length, and KMP finds b inside a + a.
• KMP or Rabin Karp? KMP is always O(n + m) with no bad luck. Rabin Karp is simpler to extend to many patterns or 2D grids, but can be slow on hash collisions.
• What is the Z algorithm? Another linear way. z[i] is how long the string starting at i matches the start of the whole string. Search with pattern + "$" + text.

Remember this

Grown-up words: the cheat sheet is the lps array (also called the prefix function or failure function), the two fingers are the text index and pattern index, and the handshake trick is the Knuth Morris Pratt algorithm.