Longest common substring (DP-03)

You are given two strings X and Y with lengths m and n. You need to find the length of the longest common substring.

Sample Input: X = “neardycoderisaprogrammingsite”, Y = “iamanerdycoder”
Expected Output: 10
Explanation: The longest common substring here is “nerdycoder” of length 10.

Algorithm:

  1. Let m and n be the length of the strings X and Y.
  2. This problem can be solved using dynamic programming since it has both optimal substructure and overlapping subproblem.
  3. We initialize a max_ variable which will store the length of the longest common substring.
  4. Create a 2D array DP of size (m+1, n+1) and initialize it with 0.
  5. DP [i][j] will store the length of longest common substring for strings X[1…i] and Y[1…j].
  6. For every value of i and j, we do the following.
    If X[i] == Y[j], then dp[i][j] = dp[i-1][j-1] + 1. This is because, if the current characters of both the strings are same, then we increase the length of the longest common substring upto those particular characters by 1. We then update the max_ variable accordingly.
    Else, we set dp[i][j] = 0.
  7. The final answer is stored in dp[m][n].
/* Author => Raunak Jain */
#include <bits/stdc++.h>
using namespace std;

int helper(string X, string Y, int m, int n){
	if(m==0 || n==0){
		return 0;				
	}
	int max_ = INT_MIN;
	vector<vector<int>> dp(m+1, vector<int>(n+1, 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] = dp[i-1][j-1]+1;
				max_ = max(max_, dp[i][j]);
			}else{
				dp[i][j]=0;
			}
		}
	}
	return max_;
}

int main(){
	string X = "nerdycoderisaprogrammingsite"; 
	string Y = "Iamanerdycoder";
	int m = X.size();
	int n = Y.size();
	cout<<helper(X, Y, m, n);
	return 0;
}

Also take a look at another popular interview question Rod Cutting Problem.

2 comments

Leave a Reply

Your email address will not be published.