Algorithm1 Practice1 Interview

Knuth-Morris-Pratt

GuideCode Labs

Use a prefix-function fallback table to match strings in linear time without rescanning text. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Knuth-Morris-Pratt when the prompt's constraints and required operations match this shape: Use a prefix-function fallback table to match strings in linear time without rescanning text.

On this page · Precompute Prefix Suffix Fallbacks

Checking your account…

Precompute Prefix Suffix Fallbacks

Knuth-Morris-Pratt (KMP) builds a prefix table where each position stores the longest proper pattern prefix that is also a suffix ending there. This records reusable partial-match structure.

Advance without Rechecking Text

The text index never moves backward. After a mismatch, already matched text remains useful because the prefix table identifies the next pattern alignment consistent with that suffix.

Trace KMP Prefix Function

Reference

def prefix_trace(pattern):
    prefix=[0]*len(pattern);trace=[]
    for index in range(1,len(pattern)):
        length=prefix[index-1];fallbacks=[]
        while length and pattern[index]!=pattern[length]:fallbacks.append(length);length=prefix[length-1]
        if pattern[index]==pattern[length]:length+=1
        prefix[index]=length;trace.append([index,fallbacks,length])
    return trace

Practice

Implement prefix_trace(pattern). Return [index,fallbacks,prefix_length] for each index after the first.

def prefix_trace(pattern):
    pass

Public tests

Fallback through proper prefix lengths

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Fallback the Pattern on Mismatch

While matched length is positive and the next symbols differ, replace length with the prefix value before it. If symbols then match, extend by one; do not discard the current text symbol prematurely.

Find All KMP Matches

Reference

def kmp_indexes(text,pattern):
    if pattern=="":return list(range(len(text)+1))
    prefix=[0]*len(pattern)
    for index in range(1,len(pattern)):
        length=prefix[index-1]
        while length and pattern[index]!=pattern[length]:length=prefix[length-1]
        if pattern[index]==pattern[length]:length+=1
        prefix[index]=length
    matches=[];length=0
    for index,character in enumerate(text):
        while length and character!=pattern[length]:length=prefix[length-1]
        if character==pattern[length]:length+=1
        if length==len(pattern):matches.append(index-len(pattern)+1);length=prefix[length-1]
    return matches

Practice

Implement kmp_indexes(text,pattern). Return all start indexes including overlaps; empty pattern matches at every boundary.

def kmp_indexes(text,pattern):
    pass

Public tests

Reuse fallback after overlapping matches

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Handle Overlapping Matches

After a full match, record its start and fall back using the final prefix value rather than resetting to zero. This permits overlapping occurrences such as aba inside ababa.

Explain It in an Interview

Say: “The prefix table tells how much of the pattern remains valid after mismatch. Text never retreats, and pattern fallback visits each prefix length a bounded number of times.” State empty-pattern and overlapping-match semantics and O(n + m) time.

Python Version Note

Python 3.11+

The code uses standard Python syntax and containers supported by the browser Judge. The Knuth-Morris-Pratt proof does not depend on a minor Python release.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Knuth-Morris-Pratt complete workflow	`O(m)`	`O(m)`	Scan once while falling back through the already computed LPS chain on mismatch.

Space

O(m) for the focused Build a KMP Prefix Table implementation.

Assumptions

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.
The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

State the precise Knuth-Morris-Pratt invariant before coding and preserve it after every update, traversal step, or recursive return.
The retained prefix or hash state represents exactly the current candidate alignment.
Text positions already passed cannot begin an unreported match.
Maintain the best border length for the processed prefix. Preserve this claim after every transition.
Fallback through earlier borders without rescanning characters. Preserve this claim after every transition.

When To Use Or Avoid Knuth-Morris-Pratt

Use It When

Use Knuth-Morris-Pratt when this precondition is stated or can be proved: The pattern, text, equality semantics, and reusable prefix or rolling-hash state are explicit.
Use it when this maintained state removes repeated work: The retained prefix or hash state represents exactly the current candidate alignment.

Choose Another Tool When

Avoid Knuth-Morris-Pratt when this precondition is absent: The pattern, text, equality semantics, and reusable prefix or rolling-hash state are explicit.
Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The pattern, text, equality semantics, and reusable prefix or rolling-hash state are explicit.

Avoid

def kmp_prefix_table(pattern):
    pass

Use instead

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

Where you will hit this: Build a KMP Prefix Table(opens in a new tab)

Breaking the state transition

Resets to zero on mismatch and loses a shorter reusable border.

Prevent it: Preserve this proof obligation: Every skipped comparison is represented by an already verified prefix or a collision-checked hash candidate.

Avoid

def kmp_prefix_table(p):
    out=[0]*len(p); length=0
    for i in range(1,len(p)):
        if p[i]==p[length]:length+=1;out[i]=length
        else:length=0
    return out

Use instead

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

Where you will hit this: Build a KMP Prefix Table(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(m).

Avoid

def kmp_prefix_table(p):
    out=[0]*len(p); length=0
    for i in range(1,len(p)):
        if p[i]==p[length]:length+=1;out[i]=length
        else:length=0
    return out

Use instead

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

Where you will hit this: Lowest Common Ancestor in a BST(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python More on Lists(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…