Given two strings. The task is to find the length of the longest common substring.
Example 1:
Input: S1 = "ABCDGH", S2 = "ACDGHR", n = 6, m = 6
Output: 4
Explanation: The longest common substring
is "CDGH" which has length 4.
Usual longest common subsequence will require slight modification
because we are trying to find consecutive sequences that are matching.
so, dp[i][j] = 1+ dp[i-1][j-1]; if char at index i and j matches in both the strings.
For more clarity refer this link
//User function Template for Java
class Solution{
int longestCommonSubstr(String S1, String S2, int n, int m){
//we will use same approach that we used in longest common subsequence
//with slight modification
int dp[][] = new int[n+1][m+1];// 1 based indexing
//base cased
//since its 0 based indexing first row and first column will have 0 values
//top down approach
for(int i =0;i<=n;i++){
dp[i][0] = 0;
}
for(int j=0;j<=m;j++){
dp[0][j] = 0;
}
int ans = 0;
for(int i=1;i<=n;i++){
for(int j =1;j<=m;j++){
if(S1.charAt(i-1)==S2.charAt(j-1)){
dp[i][j] = 1 + dp[i-1][j-1];
ans = Integer.max(dp[i][j],ans);
}
else dp[i][j] =0;
}
}
return ans;
}
}
Top comments (0)