Skip to content

Suffix Tree Hot Sheet

Use this page when one static lowercase text should behave like a compressed substring index.

Do Not Use When

  • one exact pattern match is all you need
  • suffix order or adjacent LCP is the real object
  • many patterns are known first and a pattern trie is the cleaner view
  • online string extension is central

Choose By Signal

  • one fixed text, many substring existence / earliest-occurrence queries -> suffix-tree.cpp
  • pattern may finish in the middle of a compressed edge -> suffix tree still works; subtree metadata lives on the edge child
  • lexicographic suffix tasks -> reopen Suffix Array / LCP hot sheet
  • online all-substring aggregation -> reopen Suffix Automaton

Core Invariants

  • build on text + terminator
  • every leaf corresponds to one suffix start
  • one edge is an interval [l, r) inside the built string
  • if a pattern walk succeeds, every leaf in that final matched subtree contains the pattern as a prefix
  • earliest occurrence can be cached as subtree minimum suffix start

Main Traps

  • forgetting the unique terminator
  • matching node-by-node instead of char-by-char across an edge interval
  • assuming the walk must stop exactly at an explicit node
  • using suffix tree where suffix array is simpler and more stable to reason about

Exact Starter In This Repo

Reopen Paths