Suffix Automaton
Compress all substrings of a string into a linear-size automaton with suffix links.
Interactive visualization
Use the controls to connect the idea to concrete operations before diving into the full write-up.
Active state
max length = 2
suffix link = 0
transitions: a -> 3
All states
A compact automaton of all substrings
Each state represents an equivalence class of substring endings. Suffix links jump to the next smaller context, which is why the automaton stays linear in size.
Family
Strings
Prefix-aware structures and text-centric search strategies.
Builds on
Foundational
You can start here without another page first.
Unlocks
0 next topics
Use these follow-ups when you want to apply the current idea in a richer setting.
Learning paths
2
This topic appears in curated progressions so you can keep moving without guessing the next step.
Problem
You want a structure that captures all substrings of one string and supports rich substring analytics.
Core idea
A suffix automaton is the minimal DFA that recognizes all substrings of a string.
As you append characters one by one, you maintain states representing sets of end positions. Each state stores:
- its longest represented substring length
- a suffix link to the next smaller context
- transitions by characters
Why it matters
Suffix automata are powerful because they encode a huge amount of substring information in only linear space.
They support tasks like:
- counting distinct substrings
- finding longest common substrings
- tracing occurrence structure
Complexity
| Operation | Time |
|---|---|
| Build automaton |
Many follow-up analyses remain linear or near-linear once the automaton exists.
Key takeaways
- A suffix automaton is a compact substring machine
- Suffix links are the main structural idea; they point to the next smaller suffix context
- This structure is more compact and automaton-flavored than suffix arrays or tries
- It is rare advanced string material, but it belongs in the same serious toolbox tier
Practice problems
| Problem | Difficulty | Key idea |
|---|---|---|
| Distinct Substrings references | 🔴 Hard | Count substrings via state lengths |
| Longest Common Substring references | 🔴 Hard | Walk another string through the automaton |
| String analytics references | 🔴 Hard | State transitions and suffix links |
Relation to other topics
- Suffix Array indexes suffix order; suffix automaton indexes substring state transitions
- Aho-Corasick is another automaton, but for many patterns rather than all substrings of one text
- Manacher focuses specifically on palindromes, not general substring structure
Related directions
These topics live nearby conceptually, even if they are not direct prerequisites.
Trie (Prefix Tree)
A tree-like data structure for efficient string storage and prefix-based retrieval. Essential for autocomplete, spell checking, and word search problems.
Aho-Corasick
Match many patterns in one pass by augmenting a trie with failure links. This is multi-pattern search done at scale.
Manacher
Find the longest palindromic substring in linear time by reusing information from the rightmost known palindrome.
Suffix Array
Sort all suffixes of a string once, then answer many substring questions by binary searching the sorted order.
More from Strings
Stay in the same family when you want parallel variations of the same mental model.
KMP (Knuth-Morris-Pratt)
Search for a pattern in linear time by reusing information about its own prefixes instead of restarting after mismatches.
Rabin-Karp
Search with rolling hashes so most windows can be rejected with arithmetic instead of full character comparisons.
Trie (Prefix Tree)
A tree-like data structure for efficient string storage and prefix-based retrieval. Essential for autocomplete, spell checking, and word search problems.
Z-Algorithm
Compute how much of the global prefix matches at every position, then reuse the active Z-box to stay linear.
Paths that include this topic
Follow one of these sequences if you want a guided next step instead of open-ended browsing.
String matching
Move from prefix reuse and rolling hashes to suffix-based indexing and automata.
Substring toolkit
Compare rolling hashes, sorted suffixes, automata, and palindrome-specific structure.
From the blog
Pair the atlas with recent writing from the rest of the site when you want a broader engineering perspective alongside the topic graph.