fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define PB push_back
  5. #define FI first
  6. #define SE second
  7. #define MP make_pair
  8. #define ALL(DATAST) DATAST.begin(), DATAST.end()
  9. #define MOD 1000000007ll
  10. #define SIZE 100100ll
  11.  
  12. ll dp[1050][1050];
  13.  
  14.  
  15. int main()
  16. {
  17.     ios::sync_with_stdio(0);
  18.     cin.tie(0); cout.tie(0);
  19. #ifndef ONLINE_JUDGE
  20.     freopen("input.txt", "r", stdin);
  21.     freopen("output.txt", "w", stdout);
  22. #endif
  23.  
  24.  
  25.     string x, y;
  26.  
  27.     cin >> x >> y;
  28.  
  29.  
  30.     ll m = x.length();
  31.     ll n = y.length();
  32.  
  33.     memset(dp, 0, sizeof(dp));
  34.  
  35.     for (ll i = 1; i <= m; i++)
  36.     {
  37.         for (ll j = 1; j <= n; j++)
  38.         {
  39.             if(x[i-1]==y[j-1])
  40.                 dp[i][j] = dp[i-1][j-1]+1;
  41.             else
  42.                 dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
  43.  
  44.             // cout<<dp[i][j]<<" ";
  45.         }
  46.         // cout<<endl;
  47.     }
  48.  
  49.     string ans = "";
  50.  
  51.     ll c = n;
  52.     ll r = m;
  53.  
  54.     while(c>0 && r>0)
  55.     {
  56.         if(x[r-1]==y[c-1])
  57.         {
  58.             ans = x[r-1]+ans;
  59.             r--;
  60.             c--;
  61.         }
  62.         else if(dp[r][c]==dp[r-1][c])
  63.             r = r-1;
  64.         else if(dp[r][c]==dp[r][c-1])
  65.             c = c-1;
  66.     }
  67.  
  68.  
  69.  
  70.     cout<<ans;
  71.  
  72.     return 0;
  73.  
  74.  
  75. }
Success #stdin #stdout 0s 12076KB
comments (?)
stdin
copy 
AGGTAB
GXTXAYB
stdout
copy 
GTAB
https://ideone.com/OUo5rh
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!