Saleh127

UVA 526 / DP - Edit dis

Dec 1st, 2021 (edited)
236
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-12-01-16.33.52
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. string a,b;
  13.  
  14. ll dp[90][90],n,m,id=0;
  15.  
  16. ll cost(ll i,ll j)
  17. {
  18.     if(i==n) return m-j;
  19.     if(j==m) return n-i;
  20.  
  21.     if(dp[i][j]!=-1) return dp[i][j];
  22.  
  23.     ll ans;
  24.  
  25.     if(a[i]==b[j])
  26.     {
  27.          ans=cost(i+1,j+1);
  28.     }
  29.     else
  30.     {
  31.          ll o=1+cost(i+1,j+1);
  32.          ll p=1+cost(i+1,j);
  33.          ll q=1+cost(i,j+1);
  34.  
  35.          ans=min({o,p,q});
  36.     }
  37.  
  38.     return dp[i][j]=ans;
  39. }
  40.  
  41.  
  42.  
  43. void way(ll i,ll j)
  44. {
  45.      if(i==n)
  46.      {
  47.           while(j<m)
  48.           {
  49.                ++id;
  50.                cout<<id<<" ";
  51.                cout<<"Insert "<<j+1<<","<<b[j]<<nl;
  52.                j++;
  53.           }
  54.           return ;
  55.      }
  56.  
  57.      if(j==m)
  58.      {
  59.           while(i<n)
  60.           {
  61.                ++id;
  62.                cout<<id<<" ";
  63.                cout<<"Delete "<<j+1<<nl;
  64.                i++;
  65.           }
  66.           return ;
  67.      }
  68.  
  69.      if(a[i]==b[j]) way(i+1,j+1);
  70.  
  71.      else
  72.      {
  73.           if(dp[i][j]==dp[i+1][j]+1)
  74.           {
  75.                ++id;
  76.                cout<<id<<" ";
  77.  
  78.                cout<<"Delete "<<j+1<<nl;
  79.  
  80.                way(i+1,j);
  81.           }
  82.           else if(dp[i][j]==dp[i][j+1]+1)
  83.           {
  84.                ++id;
  85.                cout<<id<<" ";
  86.  
  87.                cout<<"Insert "<<j+1<<","<<b[j]<<nl;
  88.  
  89.                way(i,j+1);
  90.           }
  91.           else
  92.           {
  93.                ++id;
  94.                cout<<id<<" ";
  95.  
  96.                cout<<"Replace "<<j+1<<","<<b[j]<<nl;
  97.  
  98.                way(i+1,j+1);
  99.           }
  100.      }
  101.  
  102.      return;
  103.  
  104. }
  105.  
  106.  
  107. int main()
  108. {
  109.     ios_base::sync_with_stdio(0);
  110.     cin.tie(0);
  111.     cout.tie(0);
  112.  
  113.      ll ss=0;
  114.  
  115.      while(getline(cin,a))
  116.      {
  117.           getline(cin,b);
  118.  
  119.           n=a.size();
  120.           m=b.size();
  121.  
  122.           memset(dp,-1,sizeof dp);
  123.  
  124.           if(ss) cout<<nl;
  125.  
  126.           cout<<cost(0,0)<<nl;
  127.  
  128.           way(0,0);
  129.  
  130.           ss++;
  131.  
  132.           id=0;
  133.  
  134.      }
  135.      return 0;
  136.  
  137. }
  138.  
  139.  
RAW Paste Data