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
- If
s[i]!=t[j]
, thendp[i][j]=0
(definition of dp[i][j]) - If
s[i]==t[j]
, thendp[i][j] = dp[i-1][j-1] + 1
Code
Time Complexity: O(n*m)