DEV Community

Prashant Mishra
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.

Enter fullscreen mode Exit fullscreen mode

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;
    }

}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)