fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, dp[1005][1005];
  5. pair<int, int> trace[1005][1005];
  6. string s, t;
  7.  
  8. bool maximize(int &x, const int &y) {
  9.     if (x < y) {
  10.         x = y;
  11.         return true;
  12.     }
  13.     return false;
  14. }
  15.  
  16. int main() {
  17. 	ios::sync_with_stdio(false); cin.tie(nullptr);
  18. 	cin >> s;
  19. 	n = s.size();
  20. 	memset(dp, 0, sizeof(dp));
  21.     t = s; reverse(t.begin(), t.end());
  22.     s = " " + s; t + " " + t;
  23.     for (int i = 1; i <= n; ++i) {
  24.         for (int j = 1; j <= n; ++j) {
  25.             dp[i][j] = dp[i - 1][j];
  26.             trace[i][j] = {i - 1, j};
  27.  
  28.             if (maximize(dp[i][j], dp[i][j - 1]))
  29.                 trace[i][j] = {i, j - 1};
  30.  
  31.             if (s[i] == t[j])
  32.                 if (maximize(dp[i][j], dp[i - 1][j - 1] + 1))
  33.                     trace[i][j] = {i - 1, j - 1};
  34.         }
  35.     }
  36.  
  37.     // cout << dp[n][n] << '\n';
  38.     string ans;
  39.     for (int x = n, y = n; x && y; tie(x, y) = trace[x][y])
  40.         if (s[x] == t[y]) ans += s[x];
  41.     cout << ans << '\n';
  42. 	return 0;
  43. }
Success #stdin #stdout 0.01s 9204KB
comments (?)
stdin
copy 
cbbd
stdout
copy 
bb
https://ideone.com/q8lEh9
language:
C++14 (gcc 8.3)
created:
3 days 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!