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

s1=abcef
s2=zbcdf

Longest Common Substring  => bcf  =>length =>3

method 1: recursion:
c++ implementation:
int rec(string x, string y, int n, int m)
{
if(n==0 ||  m==0)
return 0;
else if(x[n-1]==y[m-1])
return rec(x,y,n-1,m-1)+1;
else
return max(rec(x,y,n-1,m),rec(x,y,n,m-1));
}

int longestCommonSubsequence(string x, string y)
{
return rec(x,y,x.length(),y.length());
}

method 3 : dynamic programming
c++ implementation:

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

darkmode