KMP Failure Table

Start from brute force

The obvious approach computes each entry from its definition: for every i, try lengths L from i down to 1 and stop at the first L where pattern[:L] == pattern[i-L+1:i+1]. It works because, counting down, the first length that matches is the longest proper border. It costs O(m³) time in the worst case (up to m lengths at each of m positions, each check up to m characters) and O(m) space for the slices. It is too slow because position i learns nothing from position i − 1: on "a" * 500 + "b" + "a" * 500 (1,001 characters) it makes about 63 million character comparisons, against about 2,500 for the linear build.

The approach

The insight is that borders nest. If pattern[0..i] has a border of length L, dropping its last character leaves a border of length L − 1 of pattern[0..i-1]. So the candidates for lps[i] are the borders of the previous prefix, each extended by one character, and those borders are already in the table: the longest is k, the next is lps[k-1], then lps[lps[k-1]-1], and so on. The invariant: at the top of iteration i, k = lps[i-1].

The reference starts with lps = [0] * n and k = 0 and walks i from 1. While k > 0 and pattern[i] != pattern[k], it falls back with k = lps[k - 1], trying the next-shorter border. If pattern[i] == pattern[k], the border extends and k += 1. Either way it records lps[i] = k. It only reaches zero when the whole chain of borders is used up.

Walk through an example

Trace on "aabaaab", the third example, because index 5 shows a fallback that lands on a shorter border instead of zero; the last column read top to bottom is the answer [0, 1, 0, 1, 2, 2, 3].

Complexity

Two-pointer build: O(m) time, because k rises by at most 1 per index and every fallback lowers it, so the while loop runs at most m − 1 times in total; O(m) space for lps and O(1) besides. Brute force: O(m³) time in the worst case, from m lengths tried at m positions with checks of up to m characters, and O(m) space.

Edge cases to test

• A single character, "a": the loop never runs and the answer is [0].
• No character repeats, "abcd": [0, 0, 0, 0].
• All the same, "aaaa": [0, 1, 2, 3]; every index extends and nothing falls back.
• "aaab" must give [0, 1, 2, 0]: the b falls back twice, 2 → 1 → 0. Writing the fallback as a single if stops at k = 1 and records [0, 1, 2, 1].
• "aabaaa" must give [0, 1, 0, 1, 2, 2]. Resetting k to 0 on a mismatch throws away the border "a" and records 1 at the last index.

Common mistakes

• Off-by-one in “proper prefix” — it excludes the whole string.
• Resetting the length to 0 on a mismatch instead of falling back through the table.
• Using if instead of while for the fallback: one step back is not always enough, and "aaab" comes out as [0, 1, 2, 1].
• Blurring the table-build with the search loop — build first, then match.

Follow-ups an interviewer asks next

Use the table to find every occurrence of the pattern in a text.

Run the same loop over the text with j as the matched length: while j > 0 and the text character differs from pattern[j], set j = lps[j - 1]; on equality, j += 1. When j reaches m, record a match starting at i - m + 1 and set j = lps[m - 1] so overlapping matches are found. The text pointer never moves backward, so the search is O(n) after the O(m) build.

Does the string consist of a repeated substring?

Use the last entry. The shortest period is p = m - lps[m - 1], and the string is a whole number of copies of its first p characters exactly when lps[m - 1] > 0 and p divides m. For "ababab", lps[5] = 4, so p = 2 and the string is "ab" three times; for "aabaa", p = 3 does not divide 5.

Search for many patterns at once.

Running KMP once per pattern costs a full pass over the text per pattern. Aho-Corasick generalizes the failure table to a trie of all the patterns: each node gets a failure link to the longest proper suffix of its string that is also a path in the trie, and one pass over the text finds every occurrence of every pattern in O(n + total pattern length + matches).

Can you skip writing a separate search loop?

Yes: build the table of pattern + "#" + text, with a separator that occurs in neither string. Every index whose entry equals m is the end of an occurrence. The separator caps every entry at m, because a border longer than m would need a second separator in the string.

Where this shows up

The failure table is the heart of KMP string matching — it is why KMP runs in O(n + m) and its text pointer never moves backward, which also means it can match a stream without buffering or backing up. Generalized from one pattern to a trie of many, the same failure links become Aho-Corasick, the multi-pattern matcher used in keyword scanners and intrusion-detection signature matching. Border arrays like this one are also a standard tool for finding periods and repeats in strings, DNA included.

Reference solution

def failure_table(pattern):
    n = len(pattern)
    lps = [0] * n
    k = 0                            # length of current longest prefix-suffix
    for i in range(1, n):
        while k > 0 and pattern[i] != pattern[k]:
            k = lps[k - 1]           # fall back using the table itself
        if pattern[i] == pattern[k]:
            k += 1                   # extend the matched prefix
        lps[i] = k
    return lps


print(failure_table("ababab"))   # -> [0, 0, 1, 2, 3, 4]
print(failure_table("aabaa"))    # -> [0, 1, 0, 1, 2]

function failureTable(pattern: string): number[] {
  const n = pattern.length;
  const lps = new Array(n).fill(0);
  let k = 0;                         // current longest prefix-suffix length
  for (let i = 1; i < n; i++) {
    while (k > 0 && pattern[i] !== pattern[k]) k = lps[k - 1]; // fall back
    if (pattern[i] === pattern[k]) k++;                         // extend
    lps[i] = k;
  }
  return lps;
}

console.log(failureTable("ababab")); // -> [0,0,1,2,3,4]
console.log(failureTable("aabaa"));  // -> [0,1,0,1,2]