Longest Common Substring using Dynamic Programming

«
»

This is a C++ Program that Solves Longest Common Substring Problem using Dynamic Programming technique.

Problem Description

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.

Problem Solution

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.

Expected Input and Output

Case-1:

str1 - PABCD
str2 - MNABCPA
length of longest common substring - 3 for substring ABC
Program/Source Code

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.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
  1. #include<iostream>
  2. #include<string>
  3. #include<vector>
  4.  
  5. using namespace std;
  6.  
  7. int longestCommonSubstring(string str1, string str2)
  8. {
  9.     int len1=str1.length();
  10.     int len2=str2.length();
  11.  
  12.     //matrix to store results of subproblems 
  13.     int dp[len1+1][len2+1];
  14.  
  15.     int i,j;
  16.  
  17.     //initialization
  18.     //length of common substring is zero if either one of the substring is empty
  19.     for(i=0;i<=len1;i++)
  20.         dp[i][0]=0;
  21.  
  22.     for(j=1;j<=len2;j++)
  23.         dp[0][j]=0;
  24.  
  25.     int mx=0;
  26.  
  27.     for(i=1;i<=len1;i++)
  28.     {
  29.         for(j=0;j<=len2;j++)
  30.         {
  31.            //if characters match
  32.            if(str1[i-1]==str2[j-1])
  33.            {
  34.                dp[i][j]=dp[i-1][j-1]+1;
  35.                mx=max(dp[i][j],mx);
  36.            }
  37.  
  38.            else
  39.                dp[i][j]=0;
  40.         }
  41.     }
  42.  
  43.     return mx;
  44. }
  45.  
  46. int main()
  47. {
  48.     string str1, str2;
  49.  
  50.     cout<<"Enter string 1 - ";
  51.     getline(cin,str1);
  52.  
  53.     cout<<"Enter string 2 - ";
  54.     getline(cin,str2);
  55.  
  56.     cout<<"Length of the longest common substring is ";
  57.     cout<<longestCommonSubstring(str1, str2);
  58.  
  59.     cout<<endl;
  60.     return 0;
  61. }
Program Explanation

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.

Take Data Structure I Mock Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Runtime Test Cases
 
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.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.