Given two strings, find the length of the longest substring that appears in both. Unlike a subsequence, a substring must be contiguous.
DSA Animator › DSA Revision › Dynamic Programming › Longest Common Substring
Remember: a mismatch resets a substring to 0. The answer is the maximum cell, wherever it is. The video solves Longest Common Substring (GFG, Medium) with the 2D String DP pattern from the Dynamic Programming topic, and you can replay every step in the interactive Longest Common Substring animation.
Given two strings, find the length of the longest substring that appears in both. Unlike a subsequence, a substring must be contiguous.
For abcde and zbcdf, the answer is 3, because bcd appears in both.
Checking every substring of one string against the other is O of n cubed or worse. Prefix tables again give a quadratic solution.
Let dp of i and j be the length of the common substring that ends exactly at character i of the first string and character j of the second. If the characters match, extend the diagonal: dp of i minus 1, j minus 1, plus 1. If they do not match, the run is broken, so the value is 0. That reset to 0 is the only difference from the subsequence version. The answer is the largest value anywhere in the table, not the bottom right cell.
The b of abcde matches the b of zbcdf, giving 1. Next, c matches c, and the diagonal gives 2. Then d matches d, and the diagonal gives 3. e and f do not match, so the run resets to 0. The largest value in the table is 3, ending at d. So the longest common substring is bcd, of length 3.
In code, create a table with an extra row and column of zeros, and a variable best. For each pair, if the characters match, set the cell to the diagonal plus 1, and update best. Otherwise leave it at 0. Return best, so it's O of m times n.
Remember: a mismatch resets a substring to 0. The answer is the maximum cell, wherever it is.