Saleh127

UVA 531 / DP - LCS

Dec 1st, 2021
424
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-12-01-19.06.08
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11. ll dp[205][205];
  12.  
  13. int main()
  14. {
  15.     ios_base::sync_with_stdio(0);
  16.     cin.tie(0);
  17.     cout.tie(0);
  18.  
  19.     string a[1000];
  20.     string b[1000];
  21.  
  22.     ll n,m,i,j,k,l;
  23.  
  24.  
  25.     while(cin>>a[0])
  26.     {
  27.         n=m=0;
  28.  
  29.         while(a[n]!="#")
  30.         {
  31.             cin>>a[++n];
  32.         }
  33.  
  34.         cin>>b[0];
  35.  
  36.         while(b[m]!="#")
  37.         {
  38.             cin>>b[++m];
  39.         }
  40.  
  41.         memset(dp,0,sizeof dp);
  42.  
  43.         for(i=1; i<=n; i++)
  44.         {
  45.             for(j=1; j<=m; j++)
  46.             {
  47.                 if(a[i-1]==b[j-1])
  48.                 {
  49.                     dp[i][j]=dp[i-1][j-1]+1;
  50.                 }
  51.                 else
  52.                 {
  53.                     dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
  54.                 }
  55.             }
  56.         }
  57.  
  58.         string ans[200];
  59.  
  60.         l=0;
  61.  
  62.         while(dp[n][m])
  63.         {
  64.             if(a[n-1]==b[m-1])
  65.             {
  66.                  ans[l]=a[n-1];
  67.                  l++;
  68.                  n--,m--;
  69.             }
  70.             else if(dp[n-1][m]>dp[n][m-1])
  71.             {
  72.                  n--;
  73.             }
  74.             else m--;
  75.         }
  76.  
  77.         for(i=l-1;i>=0;i--)
  78.         {
  79.              if(i==l-1) cout<<ans[i];
  80.              else cout<<" "<<ans[i];
  81.         }
  82.         cout<<nl;
  83.     }
  84.  
  85.     return 0;
  86. }
  87.  
  88.  
RAW Paste Data