#include<stdio.h>#include<string.h>void main(){ int i,j,m,n; char x[10],y[10],x1[10],y1[10],b[10][10]={ },ans[10]; int c[10][10]; int flag=0,wflag=1,k; int temp_i,temp_j; printf("\nEnter X sequence"); scanf("%s",x1); printf("\nEnter Y sequence"); scanf("%s",y1); m=strlen(x1); n=strlen(y1); x[0]='\0'; y[0]='\0'; for(i=1;i<=m;i++) { c[i][0]=0; x[i]=x1[i-1]; } x[i]=x1[i-1]; for(i=0;i<=n;i++) { c[0][i]=0; y[i+1]=y1[i]; } 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]='\\'; } else if((c[i-1][j])>=(c[i][j-1])) { c[i][j]=c[i-1][j]; b[i][j]='^'; } else { c[i][j]=c[i][j-1]; b[i][j]='<'; } } } printf("\n\ty"); for(j=1;j<=n;j++) { printf("\t%c",y[j]); } printf("\nx"); for(j=0;j<=n;j++) { printf("\t%d",c[j][0]); } printf("\n"); for(i=1;i<=m;i++) { printf("%c\t",x[i]); for(j=0;j<=n;j++) { printf("%d",c[i][j]); printf("%c\t",b[i][j]); } printf("\n"); }printf("\nLongest Common Sequence:\n");do{ wflag--; k=0; i=m; j=n; while(i>0 && j>0) { if(b[i][j]=='^') { if(c[i-1][j]==c[i][j-1]) { b[i][j]='<'; if(flag==0) wflag++; if(i!=m && j!=n) { flag=1; if(b[m][n]=='^') b[m][n]=='<'; else b[m][n]=='^'; } } i--; } else if(b[i][j]=='<') { if(c[i-1][j]==c[i][j-1]) { b[i][j]='^'; if(flag==0) wflag++; if(i!=m && j!=n) { flag=1; if(b[m][n]=='^') b[m][n]=='<'; else b[m][n]=='^'; } } j--; } else { ans[k]=x[i]; k++;; i--; j--; } } for(i=k-1;i>=0;i--) printf("%c",ans[i]); printf("\n"); }while(wflag!=0); printf("Length is %d\n",c[m][n]);} Output:
Comments
Post a Comment