D. Changing a String

Download Raw Clone


  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1010;
  4. string s,t;
  5. int memo[N][N];
  6. int dp(int i,int j)
  7. {
  8. //cout << s[i] << " " << t[j] << endl;
  9. if(i == s.size() && j == t.size())
  10. return 0;
  11. else if (i == s.size() || j == t.size())
  12. return 1e9;
  13. int &ret = memo[i][j];
  14. if(~ret)
  15. return ret;
  16. ret = 0;
  17. if(s[i] == t[j])
  18. ret+=dp(i+1,j+1);
  19. else
  20. {
  21. if(i>j)
  22. ret = min(dp(i+1,j)+1,dp(i+1,j+1)+1);
  23. else
  24. ret = min(dp(i,j+1)+1,dp(i+1,j+1)+1);
  25. }
  26. return ret;
  27. }
  28. void build(int i,int j)
  29. {
  30. //cout << s[i] << " " << t[j] << endl;
  31. int &ret = memo[i][j];
  32. if(s[i]==t[j])
  33. build(i+1,j+1);
  34. else
  35. {
  36. if(ret == dp(i+1,j)+1)
  37. {
  38. cout << "DELETE " << j+1 << endl;
  39. build(i+1,j);
  40. }
  41. else if(ret == dp(i+1,j+1)+1)
  42. {
  43. cout << "REPLACE " << j+1 << " " << t[j] << endl;
  44. build(i+1,j+1);
  45. }
  46. else if (ret == dp(i,j+1)+1)
  47. {
  48. cout << "INSERT " << j+1 << " " << t[j] << endl;
  49. build(i,j+1);
  50. }
  51. }
  52. }
  53. int main()
  54. {
  55. ios::sync_with_stdio(0);
  56. cin.tie(NULL);
  57. cout.tie(NULL);
  58. #ifndef ONLINE_JUDGE
  59. //freopen("input.txt", "r", stdin);
  60. //freopen("out.txt", "w", stdout);
  61. #endif // ONLINE_JUDGE
  62. cin >> s >> t;
  63. memset(memo,-1,sizeof memo);
  64. cout << dp(0,0) << endl;
  65. build(0,0);
  66. return 0;
  67. }

Raw paste data: