spider68

Printing Longest Common Subsequence

May 3rd, 2020
162
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.98 KB | None | 0 0
  1. string comman_string(string s1, string s2) {
  2.         int x=s1.length(),y=s2.length(),i,j;
  3.         int a[x+1][y+1];
  4.         memset(a,0,sizeof(a));
  5.         for(i=1;i<=x;i++)
  6.         {
  7.             for(j=1;j<=y;j++)
  8.             {
  9.                 if(s1[i-1]==s2[j-1])
  10.                 {
  11.                     a[i][j]=max(a[i-1][j-1]+s1[i-1],a[i][j-1]);
  12.                 }
  13.                 else a[i][j]=max(a[i-1][j],a[i][j-1]);
  14.             }
  15.         }
  16.         int index = a[x][y];
  17.  
  18.         char lcs[index+1];
  19.         lcs[index] = '\0';
  20.         i = m, j = n;
  21.         while (i > 0 && j > 0)
  22.         {
  23.           if (s1[i-1] == s2[j-1])
  24.           {
  25.             lcs[index-1] = s1[i-1]; // Put current character in result
  26.             i--; j--; index--;     // reduce values of i, j and index
  27.           }
  28.  
  29.           else if (a[i-1][j] > a[i][j-1])
  30.           i--;
  31.           else
  32.           j--;
  33.        }
  34.         int index = L[m][n];
  35.    
  36.         return lcs;
  37.     }
Add Comment
Please, Sign In to add comment