Advanced · Module 19 · Lesson 3
Z algorithm
Measure prefix matches from every position.
15–25 min readLesson 117 of 123
Lesson 117 of 123
1d streakTheory lesson · Step-by-step
Understand Z algorithm
Measure prefix matches from every position.
Worked approach
Trace the reasoning step by step
- 1Reuse a mirrored Z value inside the current box.
- 2Extend character comparisons beyond right.
- 3Update the box when the match reaches farther.
- 4Use pattern + separator + text for matching.
Concrete example
Compute prefix matches for "aabxaab".
- 1Z[1]=1 for "a".
- 2At index 4, substring "aab" matches the prefix for length 3.
Z[4]=3, revealing a prefix occurrence.
What must remain true (Loop Invariant)
[left,right] is the rightmost segment known to match the string prefix.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Z array
O(n)
O(n)
The right boundary only moves forward.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 Z algorithm example without looking at the trace.
- Change one input condition and explain whether the Z algorithm 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.