[Algorithm] Longest Common Substring (C++/DP/Medium)

Problem Link: https://binarysearch.com/problems/Longest-Common-Substring

Hello! Today we’ll be looking at another typical dynamic programming problem: Longest Common Substring. Notice that this is different from “Longest Common Subsequence”. A substring is a contiguous chunk of subarray while a subsequence is a subarray whose elements need not be adjacent to each other.

Longest Common Substring can be solved with a slight variation of the Longest Common Subsequence.

Let dp[i][j] = The length of the longest common substring ending at [i,j].

There are TWO important intuitions to form a recurrence relation

1. If s[i]!=t[j], then dp[i][j]=0 (definition of dp[i][j])
2. If s[i]==t[j], then dp[i][j] = dp[i-1][j-1] + 1

Code

Time Complexity: O(n*m)