SHARE
TWEET

Untitled

a guest Jul 22nd, 2019 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<stdio.h>
  2. #include<string.h>
  3.  
  4. int i,j,k,l,c[50][50];
  5. char x[50],y[50],b[50][50];
  6.  
  7. void print(int i,int j)
  8. {
  9.     if(i==0 || j==0)
  10.         return;
  11.     if(b[i][j]=='*')
  12.     {
  13.         print(i-1,j-1);
  14.         printf("%c",x[i-1]);
  15.     }
  16.     else if(b[i][j]=='^')
  17.         print(i-1,j);
  18.     else
  19.         print(i,j-1);
  20. }
  21.  
  22. void lcs()
  23. {
  24.     k=strlen(x);
  25.     l=strlen(y);
  26.     for(i=1; i<=k; i++)
  27.         c[i][0]=0;
  28.     for(j=0; j<=l; j++)
  29.         c[0][j]=0;
  30.  
  31.  
  32.     for(i=1; i<=k; i++)
  33.         for(j=1; j<=l; j++)
  34.         {
  35.  
  36.             if(x[i-1]==y[j-1])
  37.             {
  38.                 c[i][j]=c[i-1][j-1]+1;
  39.                 b[i][j]='*';
  40.             }
  41.             else if(c[i-1][j]>=c[i][j-1])
  42.             {
  43.                 c[i][j]=c[i-1][j];
  44.                 b[i][j]='^';
  45.             }
  46.             else
  47.             {
  48.                 c[i][j]=c[i][j-1];
  49.                 b[i][j]='-';
  50.             }
  51.         }
  52. }
  53.  
  54. int main()
  55. {
  56.     printf("First string:");
  57.     scanf("%s",x);
  58.     printf("Second string:");
  59.     scanf("%s",y);
  60.     printf("The LCS is: ");
  61.     lcs();
  62.     print(k,l);
  63.     printf("\n\n LCS table is\n\n");
  64.  
  65.     for(i=0;i<=k;i++)
  66.     {
  67.         for(j=0;j<=l;j++)
  68.         {
  69.             printf("%d ",c[i][j]);
  70.         }
  71.         printf("\n");
  72.     }
  73.     printf("\n\n arrow table is \n\n");
  74.     for(i=0;i<=k;i++)
  75.     {
  76.         for(j=0;j<=l;j++)
  77.         {
  78.             printf("%c ",b[i][j]);
  79.         }
  80.         printf("\n");
  81.     }
  82.  
  83.     return 0;
  84. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top