Overview
Longest Common Substring uses a recurrence that extends only matching adjacent characters, resetting when characters differ.
CoreSource checked
Longest Common Substring
Finds the longest contiguous block shared by two strings.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pattern Matching
- Difficulty
- Intermediate
- Family
- Dynamic Programming
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
contiguous matchdynamic programmingstring comparisonrolling maximum
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n m)
Average
O(n m)
Worst
O(n m)
Space
O(min(n, m))
When to Use
- Use when text search needs contiguous match.
- Use when the input matches the assumptions behind dynamic Programming.
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
- Finds the longest contiguous block shared by two strings
- Uses contiguous match and dynamic programming 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)
Substring recurrence
dp[i][j] = text1[i] = text2[j] ? dp[i−1][j−1] + 1 : 0
dp[i][j] = text1[i] == text2[j] ? dp[i-1][j-1] + 1 : 0Extends a common substring only through matching adjacent characters.
Pseudocode
- 1.Prepare the inputs and state needed for Longest Common Substring.
- 2.Apply the contiguous match step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return matches.
Canonical Example
- Input
- Longest Common Substring input with a small representative case
- Output
- Matches
- Explanation
- Longest Common Substring applies contiguous match to produce matches.
Implementation Notes
- Normalize input consistently before building indexes or comparing sequences.
- Keep the contiguous match step separate enough to test independently.
Common Pitfalls
- Changing tokenization or distance definitions changes the match result.
- Forgetting to check edge cases can make Longest Common Substring 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 Longest Common Substring.
pattern-matching-mechanismNotes
Longest Common Substring should be used with the assumptions and tradeoffs of dynamic Programming in mind.
Sources (1)
What each reference supports for this entry.
Algorithms on Strings, Trees, and Sequences
BookString algorithms reference covering Longest Common Substring recurrences, automata/indexing structures, or exact/approximate matching role.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Often paired withSuffix Automaton
Pattern Matching · Extended
Suffix automatons can compute longest common substrings efficiently.
Compare with thisRelationships
View full relationship pageConceptual neighborLongest Common Subsequence
Longest common substring requires contiguous matches.
Often paired withSuffix Automaton
Suffix automatons can compute longest common substrings efficiently.
Related Algorithms
Tags
Pattern MatchingDynamic ProgrammingStringsSequence Alignment