This is a C++ Program that Solves Longest Common Substring Problem using Dynamic Programming technique.
Given two strings, find the length of the longest common substring of both the given strings.
Note that this problem is different from longest common subsequence (LCS) problem.
This problem can be solved by using bottom up DP. Create a marix to store results of overlapping subproblems and start filling the matrix row wise. Check whether the current character of str1 matches with the current character of the str2.
Case-1:
str1 - PABCD str2 - MNABCPA length of longest common substring - 3 for substring ABC
Here is source code of the C++ Program to Solve Longest Common Substring Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int longestCommonSubstring(string str1, string str2)
{
int len1=str1.length();
int len2=str2.length();
//matrix to store results of subproblems
int dp[len1+1][len2+1];
int i,j;
//initialization
//length of common substring is zero if either one of the substring is empty
for(i=0;i<=len1;i++)
dp[i][0]=0;
for(j=1;j<=len2;j++)
dp[0][j]=0;
int mx=0;
for(i=1;i<=len1;i++)
{
for(j=0;j<=len2;j++)
{
//if characters match
if(str1[i-1]==str2[j-1])
{
dp[i][j]=dp[i-1][j-1]+1;
mx=max(dp[i][j],mx);
}
else
dp[i][j]=0;
}
}
return mx;
}
int main()
{
string str1, str2;
cout<<"Enter string 1 - ";
getline(cin,str1);
cout<<"Enter string 2 - ";
getline(cin,str2);
cout<<"Length of the longest common substring is ";
cout<<longestCommonSubstring(str1, str2);
cout<<endl;
return 0;
}
In the main function, we will take input for str1 and str2. We will pass these to the function longestCommonSubstring as parameters. This function will calculate the result using bottom up DP and return the value which is displayed on the standard output.
Case-1: $ g++ longest_common_substring.cpp $ ./a.out Enter string 1 - PABCD Enter string 2 - MNABCPA Length of the longest common substring is 3
Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.
- Get Free Certificate of Merit in Data Structure I
- Participate in Data Structure I Certification Contest
- Become a Top Ranker in Data Structure I
- Take Data Structure I Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Practice Computer Science MCQs
- Buy Data Structure Books
- Buy Programming Books
- Practice Programming MCQs
- Apply for Information Technology Internship