Longest Common Substring
Like LCS but a mismatch resets the cell to 0. The answer is the largest cell.
String DP: Longest common substring
(1, 1): 'a' against 'x'. Different letters, so no common run ends here: 0.
Cost
- Best
- O(n * m)
- Average
- O(n * m)
- Worst
- O(n * m)
- Space
- O(n * m)
Before this
Taught by the same lesson
String DP covers these too, in the same run.