## DEV Community 👩‍💻👨‍💻

Prashant Mishra

Posted on • Originally published at practice.geeksforgeeks.org

# Length of longest common substring

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.

``````//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;
}
for(int j=0;j<=m;j++){
dp[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;
}

}
`````` 