Build a KMP Prefix Table

Practice Exercise Intermediate Medium Array String Knuth-Morris-Pratt

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement kmp_prefix_table(pattern). Return the LPS length for every prefix of pattern.

Starter code

def kmp_prefix_table(pattern):
    pass

Test cases

nested-border

{
  "args": [
    "ababaca"
  ]
}

Expected: [0,0,1,2,3,0,1]

repeated

{
  "args": [
    "aaaa"
  ]
}

Expected: [0,1,2,3]

Wizard outline

Step 1: Allocate one prefix value per character
Return an empty table for an empty pattern. KMP records one longest-border length at every pattern index.
Step 2: Extend a matching border
Grow the prefix length when the next characters agree. A matching character extends the current proper prefix and suffix by one.
Step 3: Fall back to a shorter valid border
Reuse earlier prefix values after a mismatch instead of discarding all progress. The prefix table itself points to the next border candidate.

Footguns and prerequisites

Resetting length directly to zero loses reusable borders.
Incrementing the scan during fallback can skip a valid shorter border.
strings

Reviewed references

Python More on Lists

Recommended approach and implementation

Scan once while falling back through the already computed LPS chain on mismatch.

Why it works: length is the longest border for the previous prefix. A match extends it; a mismatch tests the next longest possible border from the table, so every stored value is maximal without rescanning.

def kmp_prefix_table(pattern):
    table = [0] * len(pattern)
    length = 0
    index = 1
    while index < len(pattern):
        if pattern[index] == pattern[length]:
            length += 1
            table[index] = length
            index += 1
        elif length > 0:
            length = table[length - 1]
        else:
            index += 1
    return table