Overview
Build a suffix automaton for the first string, then scan the second string while tracking the current automaton state, the current contiguous match length, and the best match seen so far.
CoreSource checked
Suffix Automaton LCS
Finds a longest common substring by scanning one string through the suffix automaton of another.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pattern Matching
- Difficulty
- Intermediate
- Family
- String Automata
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 6
- Code example
- Ready
- Visualization
- Ready
Core Concepts
suffix automatonlongest common substringsuffix linkcurrent match lengthstate transition
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n + m)
Worst
O(n + m)
Space
O(n + m)
When to Use
- Use when the target is longest common substring, not longest common subsequence.
- Use when linear-time construction and scanning are worth the automaton implementation complexity.
When Not to Use
- Avoid when gaps are allowed; use a longest-common-subsequence or alignment method instead.
- Avoid when a suffix-array LCP approach is simpler and already available.
What It Does
- Finds the longest contiguous substring shared by two strings.
- Uses suffix links to recover when the next scanned character has no transition.
- Tracks best length and end position while scanning the second string.
Use Cases
- Longest common substring queries where a suffix automaton is already useful.
- String analysis where contiguous matches matter more than edit operations or subsequences.
- Teaching how suffix links support online fallback during matching.
Inputs
- Text or sequence
- Pattern, index, or comparison sequence
Outputs
- Matches, alignment, index, or similarity value
Key Formulas (1)
Match length update
if transition exists: length = length + 1 else follow suffix links
if transition exists: length = length + 1 else follow suffix linksTracks the longest substring currently matched in the automaton.
Pseudocode
- 1.Build a suffix automaton for string A
- 2.Set state to root, currentLength to 0, and bestLength to 0
- 3.For each character c at position i in string B
- 4.While state has no c transition and state is not root, follow suffix links and shorten currentLength
- 5.If a c transition exists, take it and increment currentLength; otherwise reset to root and length 0
- 6.If currentLength exceeds bestLength, store the new length and ending position i
- 7.Return the substring of B ending at bestEnd with length bestLength
Canonical Example
- Input
- first string 'xababc', second string 'zzbabca'
- Output
- longest common substring 'babc'
- Explanation
- Scanning the second string through the automaton keeps the longest contiguous path also found in the first string.
Implementation Notes
- Build the automaton from one string before scanning the other.
- On a missing transition, follow suffix links until a transition exists or the root is reached.
- Update bestLength and bestEnd whenever the current length improves.
Common Pitfalls
- Substring means contiguous; subsequence matches with gaps are a different problem.
- When following suffix links, the current match length must shrink to the linked state's length.
- The answer position is in the scanned string, not necessarily in the automaton-building string.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow walking one string through the suffix automaton of another on a small longest common substring example.
Input:ABABABCABAB
Window:ABAB
Step 1 of 7: Build a suffix automaton for string A
pattern-matching-mechanismNotes
This method reports a contiguous match. It does not score edits, gaps, or noncontiguous subsequences.
Sources (1)
What each reference supports for this entry.
Algorithms on Strings, Trees, and Sequences
BookString algorithms reference covering Suffix Automaton LCS recurrences, automata/indexing structures, or exact/approximate matching role.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toSuffix Array
Data Structures · Core
A suffix array with LCP values can also find longest common substrings after combining the strings.
Compare with thisAlternative toSuffix Tree
Data Structures · Core
Suffix trees provide another indexed structure for longest common substring queries.
Compare with thisUsed byManber-Myers Suffix Array Construction
Pattern Matching · Core
Manber-Myers Suffix Array Construction uses Suffix Automaton LCS as a subroutine, representation, or supporting idea while doubling prefix lengths and sorting suffix ranks iteratively.
Compare with thisUsed byUkkonen Suffix Tree Construction
Pattern Matching · Core
Ukkonen Suffix Tree Construction uses Suffix Automaton LCS as a subroutine, representation, or supporting idea while maintaining active points and suffix links during online construction.
Compare with thisRelationships
View full relationship pageUsesSuffix Automaton
The LCS scan relies on transitions and suffix links from a suffix automaton.
Alternative toSuffix Array
A suffix array with LCP values can also find longest common substrings after combining the strings.
Alternative toSuffix Tree
Suffix trees provide another indexed structure for longest common substring queries.
Related Algorithms
Tags
Pattern MatchingStrings