Longest Common Subsequence

PROBLEM :

Given two sequences, find the length of longest subsequence present in both of them. Both the strings are of uppercase.

Input:
First line of the input contains no of test cases  T,the T test cases follow.
Each test case consist of 2 space separated integers A and B denoting the size of string str1 and str2 respectively
The next two lines contains the 2 string str1 and str2 .


Output:
For each test case print the length of longest  common subsequence of the two strings .


Constraints:
1<=T<=30
1<=size(str1),size(str2)<=100


Example:
Input:
1
6 6
ABCDGH
AEDFHR

Output:
3

Explanation
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

// This implementation won't work if the length of string is long
// Better use Dynamic Programming

#include<iostream>
using namespace std;
int Longest_Common_Subsequence(char [],char [],int ,int ) ;
int max(int ,int ) ;
int main()
 {
int t,n1,n2,i,ans ;
char str1[100],str2[100] ;
cin>>t ;
while(t--)
{
   cin>>n1>>n2 ;
 
   for(i=0;i<n1;i++)
       cin>>str1[i] ;
     
   for(i=0;i<n2;i++)
       cin>>str2[i] ;
     
   ans=Longest_Common_Subsequence(str1,str2,n1,n2) ;
   cout<<ans ;
 
   cout<<endl ;
}
return 0;
}

int Longest_Common_Subsequence(char str1[],char str2[],int n1,int n2)
{
    if(n1==0||n2==0)
        return 0 ;
       
    if(str1[n1-1]==str2[n2-1])
        return 1+Longest_Common_Subsequence(str1,str2,n1-1,n2-1) ;
    else
        return max(Longest_Common_Subsequence(str1,str2,n1,n2-1),Longest_Common_Subsequence(str1,str2,n1-1,n2)) ;
}

int max(int a,int b)
{
    return a>b?a:b ;
}

--------------------------------------------------------------------------------
BETTER c++ IMPLEMENTATION : ( Using Dynamic Programming )
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
int Longest_Common_Subsequence(char [],char [],int ,int ) ;
int max(int ,int ) ;
int main()
 {
int t,n1,n2,i,ans ;
char str1[100],str2[100] ;
cin>>t ;
while(t--)
{
   cin>>n1>>n2 ;
 
   for(i=0;i<n1;i++)
       cin>>str1[i] ;
     
   for(i=0;i<n2;i++)
       cin>>str2[i] ;
     
   ans=Longest_Common_Subsequence(str1,str2,n1,n2) ;
   cout<<ans ;
 
   cout<<endl ;
}
return 0;
}

int Longest_Common_Subsequence(char str1[],char str2[],int n1,int n2)
{
    int mat[n1+1][n2+1] ;
    int i,j ;
   
    for(i=0;i<=n1;i++)
    {
        for(j=0;j<=n2;j++)
        {
            if (i == 0 || j == 0)
                mat[i][j] = 0;
        }
    }
   
    for(i=1;i<=n1;i++)
    {
        for(j=1;j<=n2;j++)
        {
            if(str1[i]==str2[j])
                mat[i][j]=1+mat[i-1][j-1] ;
            else
                mat[i][j]=max(mat[i-1][j],mat[i][j-1]) ;
        }
    }
   
    for(i=0;i<=n1;i++)
    {
    for(j=0;j<=n2;j++)
    cout<<mat[i][j]<<" " ;
    cout<<endl ;
}
    return mat[n1][n2] ;
}

int max(int a,int b)
{
    return a>b?a:b ;
}

---------------------------------------------------------------------------------