Advanced · Module 19 · Lesson 1
KMP & prefix function
Reuse matched-prefix information after mismatch.
15–25 min readLesson 115 of 123
Lesson 115 of 123
1d streakTheory lesson · Step-by-step
Understand KMP & prefix function
Reuse matched-prefix information after mismatch.
Worked approach
Trace the reasoning step by step
- 1Build the pattern prefix-function table.
- 2Compare text and pattern at matched.
- 3On mismatch, fall back to the longest reusable border.
- 4On a full match, report and continue from its border.
Concrete example
Search pattern "abab" inside text "ababc".
- 1Match four characters.
- 2Prefix values record reusable border lengths after future mismatch.
The pattern occurs at index 0 without rechecking matched text.
What must remain true (Loop Invariant)
matched is the length of the longest pattern prefix matching the current text suffix.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Preprocess + search
O(m + n)
O(m)
Fallback never rechecks discarded text.When to use it
- Large constraints requiring specialized string, range, geometry, or network tools.
- Repeated queries or updates that justify preprocessing.
- Problems with a strong algebraic, heuristic, or residual invariant.
Common mistakes
- Using a specialized structure without checking its operation assumptions.
- Mixing zero-based and one-based indexes.
- Memorizing formulas without proving what each stored value means.
Practice prompts
- Reproduce the worked KMP & prefix function example without looking at the trace.
- Change one input condition and explain whether the KMP & prefix function invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.