Longest Common Subsequence

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