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.

Note: Join free Sanfoundry classes at Telegram or Youtube

```
#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.

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.

« Prev - Longest Common Subsequence using Dynamic Programming

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

Next Steps:

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

Related Posts:

Practice Computer Science MCQs
Buy Data Structure Books
Buy Programming Books
Practice Programming MCQs
Apply for Information Technology Internship

Recommended Articles: