# Longest Common Subsequence

Given two strings s1 and s2. The task is to find the length of the longest common substring.

example:

example:

**s1=abcef****s2=zbcdf****Longest Common Substring => bcf =>length =>3**

**c++ implementation: we will use dynamic programming here****y is the no. of test cases:**

**#include <iostream>
using namespace std;
void lcs(string s1,string s2,int n,int w)
{
int t[n+1][w+1];
//fill 0th rows and coloumns with zero.
for(int i=0;i<=n;i++)
t[i][0]=0;
for(int j=0;j<=w;j++)
t[0][j]=0;
//comparing that particular value here s1[i-1] and s2[j-1] because of zero indexing
for(int i=1;i<=n;i++)
{
for(int j=1;j<=w;j++)
{
if(s1[i-1]==s2[j-1])
t[i][j]=t[i-1][j-1]+1;
else
t[i][j]=max(t[i-1][j],t[i][j-1]);
}
}
//max value will b present in last cell
cout<<t[n][w];
}
int main() {int y; cin>>y;
while(y--)
{ int n; int w;
cin>>n>>w;
string s1;
string s2;
cin>>s1>>s2;
lcs(s1,s2,n,w);
cout<<endl;
}
return 0;
}**