Sunday 9 March 2014

Program In C++ To Find Longest Common Sub sequence (LCS)

#include<iostream.h>
#include<conio.h>
#include<process.h>
int b[100][100],c[100][100];
void PRINT_LCS(int b[100][100],int x[],int i,int j)
{
 if(i==0||j==0)
 {return;}
 if(b[i][j]==0)
 {
  PRINT_LCS(b,x,i-1,j-1);
  cout<<x[i]<<"\t";
 }
  else if(b[i][j]==1)
  {
   PRINT_LCS(b,x,i-1,j);
  }
  else
  {
   PRINT_LCS(b,x,i,j-1);
  }
}

void LCS_LENGTH(int x[], int y[],int lenx,int leny)
{
 int i,j,b[100][100],c[100][100],m=lenx,n=leny;

 for(i=0;i<=m;i++)
 {c[i][0]=0;}

 for(j=0;j<=n;j++)
 {c[0][j]=0;}

 for(i=1;i<=m;i++)
 {
  for(j=1;j<=n;j++)
  {
   if(x[i]==y[j])
   {
    c[i][j]=c[i-1][j-1]+1;
    b[i][j]=0;
   }
   else if(c[i-1][j]>=c[i][j-1])
   {
    c[i][j]=c[i-1][j];
    b[i][j]=1;
   }
   else
   {
    c[i][j]=c[i][j-1];
    b[i][j]=2;
   }
  }
 }
 PRINT_LCS(b,x,lenx,leny);
}
void main()
{ clrscr();
 int x[100],y[100],lenx,leny;
 cout<<"Enter the length of first sequence(x) : ";
 cin>>lenx;
 cout<<"Enter x";
 for(int i=1;i<=lenx;i++)
 cin>>x[i];
 cout<<"Enter the length of second sequence(y) : ";
 cin>>leny;
 cout<<"Enter y";
 for(int j=1;j<=leny;j++)
 cin>>y[j];
 cout<<"\nLongest Common Subsequence Is: ";
 LCS_LENGTH(x,y,lenx,leny);
 getch();
}

No comments:

Post a Comment