Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<string.h>
- void out(char b[100][100],char x[],int m,int n)
- {
- char h[100];
- int i=m;
- int j=n;
- int z=0;
- for(j;j>=1;){
- if(b[i][j]=='C'){
- h[z++]=x[i-1];
- i--;
- j--;
- }
- else if(b[i][j]=='U'){
- i--;
- }
- else{
- j--;
- }
- }
- h[z]='\0';
- strrev(h);
- printf("Most sequence:");
- puts(h);
- }
- void LCS(char x[],char y[],int m,int n)
- {
- int c[100][100];
- char b[100][100];
- int i,j;
- for(i=1;i<=m;i++){
- c[i][0]=0;
- b[i][0]='X';
- }
- for(j=0;j<=n;j++){
- c[0][j]=0;
- b[0][j]='X';
- }
- for(i=1;i<=m;i++){
- for(j=1;j<=n;j++){
- if(x[i-1]==y[j-1]){
- c[i][j]=c[i-1][j-1]+1;
- b[i][j]='C';
- }
- else if(c[i-1][j]>=c[i][j-1]){
- c[i][j]=c[i-1][j];
- b[i][j]='U';
- }
- else{
- c[i][j]=c[i][j-1];
- b[i][j]='L';
- }
- }
- }
- for(i=0;i<=m;i++){
- for(j=0;j<=n;j++){
- printf("%d ",c[i][j]);
- }
- printf("\n");
- }
- printf("\n");
- for(i=0;i<=m;i++){
- for(j=0;j<=n;j++){
- printf("%c ",b[i][j]);
- }
- printf("\n");
- }
- out(b,x,m,n);
- }
- int main()
- {
- char x[100],y[100];
- printf("Enter 1st string:");
- gets(x);
- printf("Enter 1st string:");
- gets(y);
- int m=strlen(x);
- int n=strlen(y);
- LCS(x,y,m,n);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement