Skip to content

Strings -> Suffix Automaton

Compact automaton of all substrings, with endpos classes, clones, and counting applications.

  • Topic slug: strings/suffix-automaton
  • Tutorial page: Open tutorial
  • Ladder page: Open ladder
  • Repo problems currently tagged here: 1
  • Repo companion pages: 0
  • Curated external problems: 8

Microtopics

  • endpos-equivalence
  • suffix-links
  • clone-states
  • distinct-substrings
  • occurrence-counts
  • kth-substring

Learning Sources

Source Type
cp-algorithms suffix automaton Reference
USACO Guide string suffix structures Reference

Practice Sources

Source Type
CSES Distinct Substrings Practice
CSES Substring Order I Practice

Curated External Problems

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Distinct Substrings CSES Medium Counting - - Substrings; States; Endpos Distinct-substring counting is one of SAM’s core uses.
Good Substrings Codeforces Medium - Enumeration; Deduplication Suffix Automaton; Distinct Substring Counting Distinct Substrings; Trie Not only hash/trie territory; suffix automaton also fits naturally.
Repeating Substring CSES Medium Longest-Repeat - - Repeat; Substring; Suffix-Structure Another canonical SAM application with strong overlap.
suffix_automaton Library Checker Medium String-Indexing - - States; Transitions Direct official SAM construction benchmark.
Substring Order I CSES Hard Kth-Substring - - Ranking; Distinct-Substrings; Advanced K-th substring ranking is a strong suffix-structure benchmark.

Challenge

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
A Trivial String Problem Codeforces Hard - Query Processing; Hybrid Techniques Suffix Automaton; Hashing Hashing Modern hard string problem where suffix structures are a key ingredient.
Cyclical Quest Codeforces Hard - String Compression; Counting Suffix Automaton; String Rotation Intuition Cyclic Strings; Counting A standard suffix automaton problem for counting cyclic matches.
Martian Strings Codeforces Hard - Multi-Pattern Checking Suffix Automaton; Substring Occurrence Substring Queries; Pattern Matching A classic suffix-structure problem with a strong automaton solution.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
DISTINCTSUBSTRINGS Distinct Substrings primary medium suffix automaton construction; clone states; state contribution counting Note Code

Regeneration

python3 scripts/generate_problem_catalog.py