Vibe Engines Learn
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
  1. lps[0] = 0 always. Maintain k = length of the longest prefix that is also a suffix ending just before i.
  2. At position i: while k > 0 and pattern[i] != pattern[k], set k = lps[k-1] — reuse the table to fall back.
  3. If pattern[i] == pattern[k], increment k. Then set lps[i] = k.
  4. Each character advances or falls back k, so the whole thing is amortized O(n).
CPython · WebAssembly

Explore the topic

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

Algorithms & DSA