CODING CHALLENGE · N°36

KMP Failure Table

Medium StringsPattern MatchingDynamic Programming

The precomputation that makes Knuth–Morris–Pratt string search run in O(n): for every prefix of the pattern, the length of its longest proper prefix that is also a suffix. Get this table right and matching never backtracks. Build it in Python or TypeScript, with hidden tests.

The problem

Given a non-empty string pattern, return its failure table (a.k.a. the longest-proper-prefix-suffix / LPS array). Entry lps[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix of it. ("Proper" means not the whole substring.) This is the table KMP uses to skip re-comparisons after a mismatch.

EXAMPLE 1

Input pattern = 'ababab'

Output [0, 0, 1, 2, 3, 4]

"abab" has prefix "ab" = suffix "ab" → 2, and so on

EXAMPLE 2

Input pattern = 'aabaa'

Output [0, 1, 0, 1, 2]

the trailing "aa" matches the leading "aa" → 2

CONSTRAINTS

1 ≤ pattern.length; the first entry is always 0 (a single char has no proper prefix).
Build it in O(n) with the two-pointer method — do not recompute prefixes from scratch (O(n²)).
On a mismatch while extending, fall back via lps[k-1] rather than restarting at 0.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement failure_table(pattern): keep a length k of the current longest prefix-suffix. Walk i from 1; on mismatch fall back to lps[k-1]; on match extend k; record lps[i] = k.

HINTS — 4 IDEAS

lps[0] = 0 always. Maintain k = length of the longest prefix that is also a suffix ending just before i.
At position i: while k > 0 and pattern[i] != pattern[k], set k = lps[k-1] — reuse the table to fall back.
If pattern[i] == pattern[k], increment k. Then set lps[i] = k.
Each character advances or falls back k, so the whole thing is amortized O(n).

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

For each position in the pattern, record the length of the longest proper prefix that is also a suffix of the substring ending there. Build it in one pass with two indices: extend the current match when characters agree, and on a mismatch fall back to the table value (not to 0) and try again. This precomputed fallback is what lets the search skip re-comparing characters.

Complexity

Time O(m) to build the table for a pattern of length m; the search that uses it is O(n).

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.
Blurring the table-build with the search loop — build first, then match.

Where this shows up

The failure table is the heart of KMP string matching — it is why KMP runs in O(n + m) and never re-examines an input character. The same longest-prefix-that-is-a-suffix idea powers fast pattern search in editors, grep, and bioinformatics.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA