#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(); }
Sunday 9 March 2014
Program In C++ To Find Longest Common Sub sequence (LCS)
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment