Skip to content

Strings -> Suffix Tree

Compressed suffix-trie index for one static text, edge-interval matching, and subtree metadata over suffix leaves.

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

Microtopics

  • compressed-suffix-trie
  • ukkonen
  • terminator
  • edge-intervals
  • subtree-minimum
  • pattern-walk

Learning Sources

Source Type
cp-algorithms suffix tree Reference
USACO Guide string suffix structures Reference
OI Wiki suffix tree Reference

Practice Sources

Source Type
CSES Pattern Positions Practice
CSES Distinct Substrings Practice

Repo Companion Material

Material Type
Suffix Tree hot sheet quick reference
Template Library exact starter route starter route
Pattern Positions note anchor note
Suffix Array And LCP compare point
Suffix Automaton compare point

Curated External Problems

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Pattern Positions CSES Hard Substring-Index Many Queries; Suffix Processing Compressed Edges; Suffix Leaves; Subtree Minimum Earliest Occurrence; Pattern Matching The cleanest first verifier for one static text used as a compressed substring index with earliest-occurrence metadata.

Stretch

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Distinct Substrings CSES Medium - Counting; Suffix Processing Compressed Edges; Unique Terminator Distinct Substrings; Compressed Edges A good compare-point problem once the tree is trusted and you want the usable-edge-length counting view.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
PATTERNPOSITIONS Pattern Positions primary hard - Note Code

Regeneration

python3 scripts/generate_problem_catalog.py