Longest Common Substring
Vidhu
71305
Interview

Similar to Longest Common Subsequence LCS
If characters are equal : dp[i][j]=1 + dp[i-1][j-1]
else dp[i][j]=0 // this is the only change
image
Now our table contains length of al common substrings and since substrings can be found anywhere in the table, not necessarily at the end so we just need traverse the table again and find the max element that will be the lngest common substring

 int LongestCommonSubstr(string X, string Y) {
        
        int m=X.length();
        int n=Y.length();
        int dp[m+1][n+1];
        
        // initialization
        for(int i=0;i<=m;i++)
            dp[i][0]=0;   // Eg LCS of "abc" & "" = 0
        for(int j=0;j<=n;j++)
            dp[0][j]=0;   // Eg LCS of "" & "abc" = 0
        
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(X[i-1]==Y[j-1])
                    dp[i][j]=1+dp[i-1][j-1];
                else dp[i][j]=0;                   // ONLY THIS CHANGE
            }
        }
    	 int maxLen=0;              // Now finding the max element
         for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
               maxLen=max(maxLen,dp[i][j]);
        }
        return maxLen;
		}

Inroder to print it , find the element with max value and start tarversing array from that element
and keep on moving i--,j-- i.e diagnally
This way we'll keep on printing the longest common substring
Stop when we reach an element with 0 value
image

int maxLen=0;
 for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                LCSuff[i][j] = 0;
 
            else if (X[i - 1] == Y[j - 1]) {
                LCSuff[i][j] = LCSuff[i - 1][j - 1] + 1;
                if (maxLen < LCSuff[i][j]) {
                    maxLen = LCSuff[i][j];
                    Endindex=i;
                }
            }
            else
                LCSuff[i][j] = 0;
        }
    }
	return X.substr(Endindex-maxLen,maxLen);
Comments (29)