Skip to content

Strings -> KMP

Prefix-function reasoning for exact pattern matching, borders, periods, and automaton interpretations.

  • Topic slug: strings/kmp
  • Tutorial page: Open tutorial
  • Ladder page: Open ladder
  • Repo problems currently tagged here: 3
  • Repo companion pages: 0
  • Curated external problems: 5

Microtopics

  • prefix-function
  • failure-links
  • borders
  • periodicity
  • online-matching
  • automaton-view

Learning Sources

Source Type
cp-algorithms prefix function Reference
Princeton substring search Course
USACO Guide string searching Reference

Practice Sources

Source Type
CSES String Matching Practice
CSES String Functions Practice

Curated External Problems

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Finding Borders CSES Easy Borders Proof; Implementation Prefix Function Prefix-Suffix; Periods; Prefix-Function Borders are exactly the structural output KMP-style preprocessing exposes.
String Functions CSES Easy Z-Function Implementation Prefix Function; Basic String Indexing Prefix-Function; Z-Array; Pi-Array It explicitly asks for the KMP prefix-function output.
String Matching CSES Easy Pattern-Matching Implementation Prefix Function Prefix-Function; Single-Pattern; Occurrences The most direct single-pattern matching exercise for prefix-function/KMP.
Finding Periods CSES Medium Periodicity Implementation; Pattern Analysis Prefix Function; Border Chains Prefix-Function; Periods; String-Structure A canonical periodicity problem built on prefix-function reasoning.
Required Substring CSES Medium Automaton-DP - - DP; Forbidden-States; Substring-Automaton Uses the KMP automaton as the backbone of a counting DP.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
FINDINGPERIODS Finding Periods secondary easy period detection; z function prefix matches; suffix prefix coverage Note Code
STRINGFUNCTIONS String Functions secondary easy z function; prefix function; prefix structure diagnostics Note Code
STRINGMATCHING String Matching primary easy prefix function; border fallback; overlapping occurrence counting Note Code

Regeneration

python3 scripts/generate_problem_catalog.py