KMP Failure Function Application

Description

After a mismatch, naive search slides the pattern one position and starts comparing again from its first character. It re-reads text it has already seen, which is what makes it O(n × m). KMP (Knuth-Morris-Pratt) never moves backwards in the text. It precomputes, for every prefix of the pattern, the longest proper prefix that's also a suffix (the LPS array), so after a mismatch it knows how much of what it just matched can be reused. The same table answers questions about palindromes and periods without any search.

We'll go from simple to more technical:

1. The pattern: build the LPS array, falling back through borders on a mismatch.
2. The search: one pass over the text, never moving backwards, and overlapping matches.
3. A second flavor: the table on its own (palindromic prefixes, periods).
4. What breaks it: resets to zero, off-by-one fallbacks, missing separators.

The approach: building the LPS array

int[] buildLps(String p) {
    int[] lps = new int[p.length()];
    int len = 0;                                   // length of the current border
    for (int i = 1; i < p.length(); ) {
        if (p.charAt(i) == p.charAt(len)) {
            lps[i++] = ++len;                      // the border grows by one
        } else if (len > 0) {
            len = lps[len - 1];                    // fall back to the next-shorter border
        } else {
            lps[i++] = 0;
        }
    }
    return lps;
}

def build_lps(p: str) -> list[int]:
    lps = [0] * len(p)
    length = 0                                       # length of the current border
    i = 1
    while i < len(p):
        if p[i] == p[length]:
            length += 1
            lps[i] = length                          # the border grows by one
            i += 1
        elif length > 0:
            length = lps[length - 1]                 # fall back to the next-shorter border
        else:
            lps[i] = 0
            i += 1
    return lps

lps[i] is the length of the longest proper prefix of p[0..i] that is also a suffix of it - a "border". For "aabaaab" it's 0 1 0 1 2 2 3. On a mismatch, len = lps[len - 1] tries the next-longest border of what has matched so far. Resetting len = 0 instead isn't just slower - it gives wrong values: 0 1 0 1 2 1 0 for "aabaaab", missing the "aa" border at position 5.

It's O(m) in total: len increases by at most one per step of i, and every fallback decreases it, so there can be at most m fallbacks overall.

The search

int countOccurrences(String text, String pattern) {
    int[] lps = buildLps(pattern);
    int count = 0;
    for (int i = 0, j = 0; i < text.length(); i++) {        // j = pattern characters matched
        while (j > 0 && text.charAt(i) != pattern.charAt(j)) j = lps[j - 1];
        if (text.charAt(i) == pattern.charAt(j)) j++;
        if (j == pattern.length()) {
            count++;
            j = lps[j - 1];                                  // keep the overlap for the next match
        }
    }
    return count;
}

def count_occurrences(text: str, pattern: str) -> int:
    lps = build_lps(pattern)
    count = j = 0                                    # j = pattern characters matched
    for ch in text:
        while j > 0 and ch != pattern[j]:
            j = lps[j - 1]
        if ch == pattern[j]:
            j += 1
        if j == len(pattern):
            count += 1
            j = lps[j - 1]                           # keep the overlap for the next match
    return count

The text index only moves forward, so the search is O(n) and the whole algorithm O(n + m). After a full match, continuing from lps[m - 1] reuses the overlap: "aa" occurs 4 times in "aaaaa", and resetting j = 0 would count only 2.

A second flavor: the table on its own

The LPS array answers questions without any search:

• Longest palindromic prefix. Build it for s + "#" + reverse(s). The last value is the length of the longest prefix of s that is a palindrome, so s.length() minus it is the fewest characters to prepend to make s a palindrome. The # stops a match from running across the join: without it, "aaa" gives an LPS of 5 and an answer of -2.
• Smallest period. p = n - lps[n - 1]. s is a repetition of a block exactly when p < n and n % p == 0. For "abcabcab", lps ends at 5, so p = 3, but 8 isn't a multiple of 3: not a whole repetition.

Where you'll see it

Because KMP reads each text character exactly once and keeps only O(m) state, it works on streams - network packets, log tails - without buffering the text. Aho-Corasick generalizes its failure links to thousands of patterns at once, which is how intrusion-detection systems such as Snort match attack signatures. The failure function also shows up in DNA analysis, finding periodic repeats.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. What is the LPS array of "abab", and what does lps[3] = 2 mean?

2. Why is the fallback len = lps[len - 1] rather than len = 0?

3. Why does the palindrome-prefix trick need a separator between s and reverse(s)?

Key takeaways

• lps[i] = the longest proper prefix of p[0..i] that is also its suffix.
• On a mismatch, fall back to lps[len - 1]; resetting to 0 gives wrong values.
• The search never moves back in the text: O(n + m) overall.
• After a match, continue from lps[m - 1] to count overlapping occurrences.
• The table alone gives the smallest period (n - lps[n - 1]) and, with s + "#" + reverse(s), the longest palindromic prefix.