Longest Common Substring Problem

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.

```
#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;
```
```
}
```

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.

Note: Join free Sanfoundry classes at Telegram or Youtube

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.

If you find any mistake above, kindly email to [email protected]

« Prev - Longest Common Subsequence using Dynamic Programming

» Next - Maximum Value of Gifts Problem – Dynamic Programming Solutions

Related Posts:

Recommended Articles: