Advertisement
alamin54017

Longest Common Subsequence(LCS) problem

Jul 22nd, 2019
226
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.64 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<string.h>
  3. void out(char b[100][100],char x[],int m,int n)
  4. {
  5.     char h[100];
  6.     int i=m;
  7.     int j=n;
  8.     int z=0;
  9.     for(j;j>=1;){
  10.             if(b[i][j]=='C'){
  11.                 h[z++]=x[i-1];
  12.                 i--;
  13.                 j--;
  14.             }
  15.             else if(b[i][j]=='U'){
  16.                 i--;
  17.             }
  18.             else{
  19.                 j--;
  20.             }
  21.     }
  22.     h[z]='\0';
  23.     strrev(h);
  24.     printf("Most sequence:");
  25.     puts(h);
  26. }
  27. void LCS(char x[],char y[],int m,int n)
  28. {
  29.     int c[100][100];
  30.     char b[100][100];
  31.     int i,j;
  32.     for(i=1;i<=m;i++){
  33.         c[i][0]=0;
  34.         b[i][0]='X';
  35.     }
  36.     for(j=0;j<=n;j++){
  37.         c[0][j]=0;
  38.         b[0][j]='X';
  39.     }
  40.     for(i=1;i<=m;i++){
  41.         for(j=1;j<=n;j++){
  42.             if(x[i-1]==y[j-1]){
  43.                 c[i][j]=c[i-1][j-1]+1;
  44.                 b[i][j]='C';
  45.             }
  46.             else if(c[i-1][j]>=c[i][j-1]){
  47.                 c[i][j]=c[i-1][j];
  48.                 b[i][j]='U';
  49.             }
  50.             else{
  51.                 c[i][j]=c[i][j-1];
  52.                 b[i][j]='L';
  53.             }
  54.         }
  55.     }
  56.     for(i=0;i<=m;i++){
  57.         for(j=0;j<=n;j++){
  58.             printf("%d ",c[i][j]);
  59.         }
  60.         printf("\n");
  61.     }
  62.     printf("\n");
  63.     for(i=0;i<=m;i++){
  64.         for(j=0;j<=n;j++){
  65.             printf("%c ",b[i][j]);
  66.         }
  67.         printf("\n");
  68.     }
  69.     out(b,x,m,n);
  70.  
  71.  
  72. }
  73. int main()
  74. {
  75.     char x[100],y[100];
  76.     printf("Enter 1st string:");
  77.     gets(x);
  78.     printf("Enter 1st string:");
  79.     gets(y);
  80.     int m=strlen(x);
  81.     int n=strlen(y);
  82.     LCS(x,y,m,n);
  83.  
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement