AlgoScope

Longest Common Substring

Like LCS but a mismatch resets the cell to 0. The answer is the largest cell.

Dynamic programming, algorithm, intermediate
Cell 1, 1 compares a with x and becomes 0.xyzabcdabcdxyz0000000000000000
Cell 1, 1 compares a with x and becomes 0.xyzabcdabcdxyz0000000000000000

String DP: Longest common substring

Decision, step 2 of 51

(1, 1): 'a' against 'x'. Different letters, so no common run ends here: 0.

How string dp works

Cost

Best
O(n * m)
Average
O(n * m)
Worst
O(n * m)
Space
O(n * m)

Taught by the same lesson

String DP covers these too, in the same run.