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)