Overview
A suffix automaton stores equivalence classes of substrings, supporting substring queries and many string-counting tasks.
ExtendedSource checked
Suffix Automaton
Represents all substrings of a string in a compact deterministic automaton.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pattern Matching
- Difficulty
- Advanced
- Family
- String Automaton
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
substring automatonsuffix linkstate extensionend position class
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(n)
When to Use
- Use when text search needs substring automaton.
- Use when the input matches the assumptions behind string Automaton.
When Not to Use
- Avoid when a simpler exact search is enough and approximate scoring is unnecessary.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Represents all substrings of a string in a compact deterministic automaton
- Uses substring automaton and suffix link to guide the work.
- Produces matches.
Use Cases
- Text search
- Sequence comparison
- Similarity detection
Inputs
- Pattern or query sequence
- Text or target sequence
Outputs
- Matches
- Score
- Alignment or index
Key Formulas (1)
Distinct substrings
count = sumstate (len[state] − len[link[state]])
count = sum_state (len[state] - len[link[state]])Counts substrings represented by each automaton state.
Pseudocode
- 1.Prepare the inputs and state needed for Suffix Automaton.
- 2.Apply the substring automaton step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return matches.
Canonical Example
- Input
- Suffix Automaton input with a small representative case
- Output
- Matches
- Explanation
- Suffix Automaton applies substring automaton to produce matches.
Implementation Notes
- Normalize input consistently before building indexes or comparing sequences.
- Keep the substring automaton step separate enough to test independently.
Common Pitfalls
- Changing tokenization or distance definitions changes the match result.
- Forgetting to check edge cases can make Suffix Automaton look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow matched positions, dynamic-programming cells, or candidate buckets.
Input:ABABABCABAB
Window:ABAB
Step 1 of 4: Prepare the inputs and state needed for Suffix Automaton.
pattern-matching-mechanismNotes
Suffix Automaton should be used with the assumptions and tradeoffs of string Automaton in mind.
Sources (2)
What each reference supports for this entry.
Algorithms on Strings, Trees, and Sequences
BookString algorithms reference for Suffix Automaton's pattern matching, suffix indexing, alignment, or sequence-processing mechanism.
Open sourceIntroduction to Algorithms (CLRS)
BookTextbook support for Suffix Automaton's algorithm family, complexity framing, and standard implementation concepts.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageConceptual neighborLongest Common Substring
Suffix automatons can be used to solve longest common substring problems.
Alternative toSuffix Tree
Suffix automatons represent all substrings with a compact automaton.
Related Algorithms
Tags
Pattern MatchingAutomatonStringsSuffix Index