# 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++

### One response to “Longest Common Substring in C++ using dynamic programming”

### Leave a Reply

You must be logged in to post a comment.

it was helpful for me.