Longest Common Substring
Like LCS but a mismatch resets the cell to 0; the answer is the largest cell.
Decision · step 2 of 51String DP: Longest common substring
(1, 1): 'a' against 'x'. Different letters, so no common run ends here: 0.
What you will see
Diagonal runs of increasing numbers; the longest run is the answer.
Cost
| Best | O(n * m) |
|---|---|
| Average | O(n * m) |
| Worst | O(n * m) |
| Space | O(n * m) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Table cells announce their state and value; each step announces which cells were read and the value written.
Reduced motion: Dependency arrows appear statically and the cell value crossfades.
Before this
Taught by the same lesson
String DP covers these too, in the same run.