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)

Why You Need to Study Javascript Fundamentals

The harsh reality for JS Developers: If you don't study the fundamentals, you'll be just another β€œCoder”. Top learnings on how to get to the mid/senior level faster as a JavaScript developer by Dragos Nedelcu.