SHARE
TWEET

D. Changing a String

a guest Jul 22nd, 2019 55 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 = 1010;
  5.      
  6.     string s,t;
  7.      
  8.     int memo[N][N];
  9.      
  10.     int dp(int i,int j)
  11.     {
  12.         //cout << s[i] << " " << t[j] << endl;
  13.         if(i == s.size() && j == t.size())
  14.             return 0;
  15.         else if (i == s.size() || j == t.size())
  16.             return 1e9;
  17.         int &ret = memo[i][j];
  18.         if(~ret)
  19.             return ret;
  20.         ret = 0;
  21.         if(s[i] == t[j])
  22.             ret+=dp(i+1,j+1);
  23.         else
  24.         {
  25.             if(i>j)
  26.                 ret = min(dp(i+1,j)+1,dp(i+1,j+1)+1);
  27.             else
  28.                 ret = min(dp(i,j+1)+1,dp(i+1,j+1)+1);
  29.         }
  30.         return ret;
  31.      
  32.     }
  33.      
  34.      
  35.     void build(int i,int j)
  36.     {
  37.         //cout << s[i] << " " << t[j] << endl;
  38.         int &ret = memo[i][j];
  39.         if(s[i]==t[j])
  40.             build(i+1,j+1);
  41.         else
  42.         {
  43.             if(ret == dp(i+1,j)+1)
  44.             {
  45.                 cout << "DELETE " << j+1 << endl;
  46.                 build(i+1,j);
  47.             }
  48.             else if(ret == dp(i+1,j+1)+1)
  49.             {
  50.                 cout << "REPLACE " << j+1 << " " << t[j] << endl;
  51.                 build(i+1,j+1);
  52.             }
  53.             else if (ret == dp(i,j+1)+1)
  54.             {
  55.                 cout << "INSERT " << j+1 << " " << t[j] << endl;
  56.                 build(i,j+1);
  57.             }
  58.         }
  59.      
  60.     }
  61.      
  62.      
  63.     int main()
  64.     {
  65.         ios::sync_with_stdio(0);
  66.         cin.tie(NULL);
  67.         cout.tie(NULL);
  68.      
  69.         #ifndef ONLINE_JUDGE
  70.             //freopen("input.txt", "r", stdin);
  71.             //freopen("out.txt", "w", stdout);
  72.         #endif // ONLINE_JUDGE
  73.      
  74.         cin >> s >> t;
  75.         memset(memo,-1,sizeof memo);
  76.         cout << dp(0,0) << endl;
  77.         build(0,0);
  78.         return 0;
  79.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top