vivek_ragi

LPS

Dec 8th, 2021
983
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N =  2006;
  5. int dp[N][N];
  6. pair<int,int> bck[N][N]; //  backtracking
  7. string s;
  8.  
  9. string palindrome(int l, int r){
  10.   if(l == r){
  11.     return string(1, s[l]);
  12.   }
  13.   if(l+1 == r){
  14.     if(s[l] == s[r]){
  15.       return  string(2, s[l]);
  16.     }
  17.     else{
  18.       return "";
  19.     }
  20.   }
  21.   int ll = bck[l][r].first;
  22.   int rr = bck[l][r].second;
  23.   string ret = palindrome(ll, rr);
  24.   if(ll == l+1 and  rr == r-1){
  25.     assert(s[l] == s[r]);
  26.     return string(1,s[l]) + ret + string(1, s[r]);
  27.   }
  28.   return ret;
  29. }
  30.  
  31. int main () {
  32.     bool done = false;
  33.     while (!done) {
  34.  
  35.         getline(cin,s);
  36.         if (s == "") {
  37.             done = true;
  38.             break;
  39.         }
  40.         int n = s.size();
  41.  
  42.         for (int i = 0; i < n; ++i) {
  43.             dp[i][i] = 1;
  44.             bck[i][i] = make_pair(-1, -1);
  45.         }
  46.        
  47.         for (int len = 2; len <= n; ++len) {
  48.             for (int i = 0; i + len < n + 1; ++i) {
  49.                 int j = i + len - 1;
  50.                
  51.                 if (s[i] == s[j] and len == 2) {
  52.                     dp[i][j] = 2;
  53.                     bck[i][j] = make_pair(-1, -1);
  54.                 }
  55.                 else if (s[i] == s[j]) {
  56.                   bck[i][j] = make_pair(i+1, j-1);
  57.                     dp[i][j] = dp[i+1][j-1] + 2;
  58.                    
  59.                 }
  60.                 else {
  61.                     if(dp[i+1][j] > dp[i][j-1]){
  62.                       bck[i][j] = make_pair(i+1, j);
  63.                     }else{
  64.                       bck[i][j] = make_pair(i, j-1);
  65.                     }
  66.                  
  67.                     dp[i][j] = max (dp[i + 1][j], dp[i][j - 1]);
  68.                 }
  69.             }
  70.         }
  71.  
  72.         cout << dp[0][n-1] << "\n";
  73.         cout << palindrome(0, n - 1);
  74.     }
  75.    
  76.     return 0;
  77. }
RAW Paste Data