Longest Common Substring
The problem of finding the longest contiguous string shared by two input strings.
Longest Common Substring is different from Longest Common Subsequence: matched symbols must remain contiguous in both inputs. That distinction matters in diff-like workloads, content similarity, and biological sequence processing.
Implementation Note
The straightforward dynamic-programming formulation runs in O(m*n) time. Space can be reduced to O(min(m,n)) when only the previous row is retained. For repeated searches over a large corpus, suffix-tree, suffix-array, or suffix-automaton indexing can be a better fit than rebuilding a DP table per query.
If the actual substring is required rather than only its length, the implementation must retain an end position or equivalent reconstruction state.
Related Concepts
- Edit Distance
- Suffix Array
- Suffix Automaton
- Dynamic Programming