Z-Function Ladder

Who This Is For

Use this ladder when prefix-match problems keep showing up and you want a cleaner alternative to KMP for that viewpoint.

Warm-Up

• build the Z array
• pattern matching through concatenation

Core

• prefix-match reasoning
• periodicity and borders

Repo Anchors

• String Functions
• Finding Periods

These two notes give a nice progression:

• String Functions stabilizes the Z-array mechanics
• Finding Periods turns that array into a real structure-detection tool

Exit Criteria

You are ready to move on when you can:

• maintain the [l, r) invariant correctly
• explain why the algorithm is linear
• use pattern + '#' + text confidently
• recognize when the prefix viewpoint is cleaner than KMP

External Practice

• CP-Algorithms - Z-Function
• OI Wiki - Z Function

Tutorial Link

• Z-Function