Overview
Longest Common Substring finds the longest run of characters appearing consecutively in both strings. It uses the same table as Longest Common Subsequence with a single rule changed, and that one change is the whole difference between the two problems.
In LCS, a mismatch carries the best result so far sideways: the cell takes the larger of its neighbours. Here a mismatch resets the cell to 0, because a substring cannot have a gap in it. The consequence is that the answer is no longer in the bottom-right corner — it is the largest value anywhere in the table, and you have to track it as you fill.
How Longest Common Substring works
- Build a table of size (m+1) × (n+1), where row i and column j represent prefixes of the two strings, with row 0 and column 0 filled with zeros.
- For each pair of positions, compare the two characters.
- If they match, set the cell to the diagonal cell above-left plus one — extending the run that ended at the previous pair.
- If they do not match, set the cell to 0. The run is broken and nothing carries across.
- Track the maximum value and its position while filling; the substring is read backwards from that position for that many characters.
When to use it
- Plagiarism and duplicate detection, where a shared verbatim passage matters more than scattered shared words.
- Bioinformatics — locating a conserved contiguous region in two DNA or protein sequences.
- File comparison and delta encoding, where the longest identical block is the anchor a diff is built around.
- Not the right tool when gaps are acceptable — that is Longest Common Subsequence, and the two give very different answers.
Complexity analysis
Time is O(m·n): every cell is computed once with constant work. Space is O(m·n) for the full table, but if you only need the length and not the substring itself, two rows suffice and space drops to O(min(m, n)). For very large inputs a suffix automaton or generalised suffix tree solves the same problem in linear time, at a considerable cost in implementation complexity.
Frequently asked questions
Why is the answer not in the bottom-right cell like in LCS?
Because each cell here means 'the length of the common run ending exactly at this pair of positions', not 'the best result across these prefixes'. Runs end all over the table, so the maximum can be anywhere and must be tracked separately.
What if there are several longest substrings?
Tracking a single maximum returns whichever one the fill order reaches last. To collect all of them, record every position whose value equals the maximum, then reconstruct from each.
Can the two-row space optimisation still recover the substring?
Yes, as long as you also store the end index alongside the maximum length. The substring is a contiguous slice of the original string, so an end position and a length are enough — unlike LCS, which needs the full table to walk a path back.