Skip to content

Strings -> Z-Function

Maintain a Z-box to measure longest prefix matches at every position and solve period/border problems efficiently.

  • Topic slug: strings/z-function
  • Tutorial page: Open tutorial
  • Ladder page: Open ladder
  • Repo problems currently tagged here: 2
  • Repo companion pages: 0
  • Curated external problems: 5

Microtopics

  • z-function
  • z-box
  • prefix-occurrences
  • pattern-search
  • string-periods
  • border-array

Learning Sources

Source Type
cp-algorithms Z-function Reference
USACO Guide string searching Reference

Practice Sources

Source Type
Library Checker Z Algorithm Practice
CSES String Functions Practice
CSES Finding Periods Practice

Curated External Problems

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
String Functions CSES Easy Prefix-Function Implementation Z-Function Definition String Processing; Z-Array; Pi-Array; Fundamentals This task directly computes the z-array, so it is the cleanest Z-function drill.
String Matching CSES Easy Pattern-Matching Implementation Z-Function Linear-Time String Algorithms; Single-Pattern; Occurrences; Linear-Time Single-pattern matching is a textbook Z-function application.
Finding Periods CSES Medium Periodicity Proof; Implementation Z-Function; Prefix-Suffix Structure Borders; Periods; Prefix-Structure; String-Analysis Periods can be extracted naturally from prefix comparisons that Z handles well.
Password Codeforces Medium Borders - - Prefix-Suffix; Longest-Border; Classic A textbook border problem where Z is a natural route.
Prefixes and Suffixes Codeforces Medium Border-Enumeration - - Prefixes; Suffixes; Counts Canonical Z-function task for collecting all prefix-suffix matches.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
FINDINGPERIODS Finding Periods primary easy period detection; z function prefix matches; suffix prefix coverage Note Code
STRINGFUNCTIONS String Functions primary easy z function; prefix function; prefix structure diagnostics Note Code

Regeneration

python3 scripts/generate_problem_catalog.py