Longest Common Substring in C++ using dynamic programming

In this tutorial, we will learn about how to find the longest common substring(LCS) by using a dynamic approach. We will also see the code implementation in c++ to find the longest common substring.

We will also see examples to understand the concept in a better way.

Longest Common Substring using Dynamic programming

A substring is a sequence that appears in relative order and contiguous.

In the longest common substring problem,

We have given two sequences, so we need to find out the longest substring present in both of them.




Let’s see the examples,

string_1="abcdef"
string_2="xycabc"
So, length of LCS is 3. Hence common substring is "abc".

string_1="ahkolp"
string_2="ehkolp"
So, length of LCS is 5. Hence common substring is "hkolp".

Let’s see the pseudocode,

1.let n1 and n2 is the length of two string s1 and s2.
2.Firstly declare an 2d array dp[n1+1][n2+1].
3.Run two loop for fill the entries of 2d array
    - if i==0||j==0 then do
         dp[i][j]=0
      else do
         if s1[i-1]==s2[j-1] then do
            dp[i][j]=1+dp[i-1][j-1]
         else do 
         dp[i][j]=0
4.Find max value in dp[][] is equal to LCS of these two string.

Let’s see the 2d array filling structure,

  0 a b c d a f
0 0 0 0 0 0 0 0
z 0 0 0 0 0 0 0
b 0 0 1 0 0 0 0
c 0 0 0 2 0 0 0
d 0 0 0 0 3 0 0
f 0 0 0 0 0 0 1       lCS is 3.

C++ Program to find Longest Common Substring

#include<bits/stdc++.h>
using namespace std;
int longestsub(string x,string y,int n,int m){
    int lcs[n+1][m+1];
    int result=0;//store the maximum value of 2d array
    for(int i=0;i<n+1;i++){
        for(int j=0;j<m+1;j++){
            if(i==0||j==0){
                lcs[i][j]=0;
            }
            else if(x[i-1]==y[j-1]){
            lcs[i][j]=1+lcs[i-1][j-1];
            result =max(result,lcs[i][j]);
            }
            else lcs[i][j]=0;
        }
    }
    return result;
}

int main() {
      string x="abcdaf";
      string y="zbcdf";
      int n=x.length();
      int m=y.length();
      cout<<"LCS of given strings is: "<<" ";
      cout<<longestsub(x,y,n,m)<<endl;
  
  return 0;
}

Output

LCS of given strings is: 3

You may also learn,

Solution of N-Queen problem in C++ using Backtracking

Activity Selection Problem using Greedy method in C++


Leave a Reply

Your email address will not be published. Required fields are marked *