splash365

Untitled

Nov 25th, 2021
714
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. string s;
  6. int dp[20][20], ans[20][20];
  7.  
  8. int call(int i, int j)
  9. {
  10.     if(i >= j) return 0;
  11.     if(dp[i][j] != -1) return dp[i][j];
  12.     if(s[i] == s[j])
  13.     {
  14.         ans[i][j] = 0; // 0 means no insert
  15.         return dp[i][j] = call(i+1, j-1);
  16.     }
  17.     int res1 = 1+call(i+1, j);
  18.     int res2 = 1+call(i, j-1);
  19.     if(res1 < res2)
  20.     {
  21.         ans[i][j] = 1; // 1 means insert last
  22.         return dp[i][j] = res1;
  23.     }
  24.     else
  25.     {
  26.         ans[i][j] = 2; // 2 means insert first
  27.         return dp[i][j] = res2;
  28.     }
  29.     // return dp[i][j] = min(1+call(i+1, j), 1+call(i, j-1));
  30. }
  31.  
  32. string print(int i, int j, string k, int l, int r)
  33. {
  34.     if(ans[i][j] == -1) return k;
  35.     if(ans[i][j] == 0) return print(i+1, j-1, k, l, r);
  36.     if(ans[i][j] == 1)
  37.     {
  38.         string res = "";
  39.         for(int p = 0; p<=j+l; p++) res += k[p];
  40.         res += s[i];
  41.         for(int p=j+l; p<k.size()-r; p++) res += k[p];
  42.         k = res;
  43.         cout << k << endl;
  44.         return print(i+1, j, k, l, r+1);
  45.     }
  46.     else
  47.     {
  48.         string res = "";
  49.         for(int p = 0; p<i+l; p++) res += k[p];
  50.         res += s[j];
  51.         for(int p=i+l; p<k.size()-r; p++) res += k[p];
  52.         k = res;
  53.         cout << k << endl;
  54.         return print(i, j-1, k, l+1, r);
  55.     }
  56. }
  57.  
  58. int main() {
  59.     cin >> s;
  60.     memset(dp, -1, sizeof(dp));
  61.     memset(ans, -1, sizeof(ans));
  62.     cout << call(0, s.size()-1) << endl;
  63.     for(int i = 0; i<s.size(); i++)
  64.     {
  65.         for(int j = 0; j<s.size(); j++)
  66.         {
  67.             printf("%4d", ans[i][j]);
  68.         }
  69.         cout << endl;
  70.     }
  71.     cout << print(0, s.size()-1, s, 0, 0) << endl;
  72. }
  73.  
  74.  
RAW Paste Data