Lesson 35.1 · Advanced String Algorithms

KMP: Never Re-Read the Text

The failure table lps[i] stores the longest proper prefix of the pattern that is also a suffix of pattern[0..i]. On a mismatch, jump back to that prefix instead of restarting.

18 min

Think of it like this

Typing a door code "1213" and pressing 1-2-1-2 by mistake. You don't have to start over: the last "12" you typed is already the start of the code, so you continue from there.

1.Why brute force wastes work

Brute force aligns the pattern at every position and compares. After matching "ababa" and failing on the next character, it shifts by one and compares characters it has already seen. KMP uses the pattern's own structure: the matched part "ababa" ends with "aba", which is also its prefix, so the pattern can continue as if "aba" is already matched.

2.Building the failure table

lps[i] (longest proper prefix that is also a suffix) is built with two pointers: len is the current matched prefix length. If p[i] == p[len], extend: lps[i] = ++len. On a mismatch with len > 0, fall back to len = lps[len − 1] and try again; with len == 0, lps[i] = 0.

Searching uses the same fall-back rule on the text. Each step either advances the text pointer or shrinks len, so both phases are linear: O(n + m) total.

Main.java

import java.util.*;

public class Main {
    static int[] lps(String p) {
        int[] lps = new int[p.length()];
        for (int i = 1, len = 0; i < p.length(); ) {
            if (p.charAt(i) == p.charAt(len)) lps[i++] = ++len;
            else if (len > 0) len = lps[len - 1];
            else lps[i++] = 0;
        }
        return lps;
    }

    public static void main(String[] args) {
        String text = "abababacaba", p = "ababaca";
        int[] lps = lps(p);
        System.out.println("lps = " + Arrays.toString(lps));
        List<Integer> found = new ArrayList<>();
        for (int i = 0, j = 0; i < text.length(); i++) {
            while (j > 0 && text.charAt(i) != p.charAt(j)) j = lps[j - 1];
            if (text.charAt(i) == p.charAt(j)) j++;
            if (j == p.length()) { found.add(i - j + 1); j = lps[j - 1]; }
        }
        System.out.println("matches at " + found);
    }
}

Output

lps = [0, 0, 1, 2, 3, 0, 1]
matches at [2]

▶ Dry run: lps for "ababaca"pattern = "ababaca"

lps(list)

Step 1/5lps[0] = 0 always (a proper prefix can't be the whole string).

Remember

lps = longest proper prefix that's also a suffix.
Mismatch: len = lps[len − 1].
O(n + m), the text pointer never moves back.

Common mistakes

Resetting j to 0 on every mismatch (that's brute force again).
Forgetting to continue after a full match (j = lps[j − 1]).

Words used in this lesson

Proper prefix: A prefix shorter than the whole string.
Failure function: Another name for the lps table: where to continue after a mismatch.

Command Palette

KMP: Never Re-Read the Text

1.Why brute force wastes work

2.Building the failure table