Advertisement
shabbyheart

print lcs using dp

Jan 12th, 2020
267
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.52 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string str1,str2;
  5. int CS[100][100];
  6.  
  7. int LCS(int str1_len,int str2_len)
  8. {
  9.     for(int i=1;i<=str1_len;i++)
  10.     {
  11.         for(int j=1;j<=str2_len;j++)
  12.         {
  13.             if(str1[i-1] == str2[j-1])
  14.                 CS[i][j] = 1 + CS[i-1][j-1];
  15.             else
  16.                 CS[i][j] = max(CS[i-1][j],CS[i][j-1]);
  17.         }
  18.     }
  19. }
  20.  
  21. int main()
  22. {
  23.     stack<char>stk;
  24.     int first_start,second_start;
  25.     cin>>str1>>str2;
  26.     LCS(str1.size(),str2.size());
  27.     cout<<"The LCS of these string = "<<CS[str1.size()][str2.size()]<<endl;
  28.  
  29.  
  30.     for(int i=0;i<=str1.size();i++)
  31.     {
  32.         for(int j=0;j<=str2.size();j++)
  33.             cout<<CS[i][j]<<" ";
  34.         cout<<endl;
  35.     }
  36.  
  37.     int mx = CS[str1.size()][str2.size()];
  38.     for(int l = str1.size();l>=1;l--)
  39.     {
  40.         if(CS[l][str2.size()]==mx)
  41.         {
  42.             int i = l;
  43.             int j = str2.size();
  44.             while(j>0 && i>0)
  45.             {
  46.                 if(CS[i][j] == CS[i][j-1])
  47.                     j = j-1;
  48.                 else if(CS[i][j] == CS[i-1][j])
  49.                     i = i-1;
  50.                 else
  51.                 {
  52.                     stk.push(str2[j-1]);   /// Alternate way stk.push(str1[i-1])
  53.                     i = i-1;
  54.                     j = j-1;
  55.                 }
  56.             }
  57.  
  58.             while(!stk.empty())
  59.             {
  60.                 cout<<stk.top();
  61.                 stk.pop();
  62.             }
  63.             cout<<endl;
  64.         }
  65.     }
  66.     return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement