fork download 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 5e3 + 5; 
  12.  
  13. int n, m;  
  14. string s, t;  
  15. int dp[N][N]; // dp[i][j] = Số thao tác ít nhất để biến đổi s[1..i] thành t[1..j] 
  16.  
  17. int main() {
  18. 	ios::sync_with_stdio(false); 
  19. 	cin.tie(nullptr);  	
  20. 	cin >> s >> t;  
  21. 	n = s.size(), m = t.size();  
  22. 	s = ' ' + s;  
  23. 	t = ' ' + t;  
  24.  
  25.  
  26. 	for (int i = 0; i <= n; i++) {
  27. 		for (int j = 0; j <= m; j++) dp[i][j] = INF; 
  28. 	}
  29.  
  30. 	dp[0][0] = 0;   
  31. 	for (int j = 1; j <= m; j++) dp[0][j] = j;   
  32. 	for (int i = 1; i <= n; i++) dp[i][0] = i;   
  33.  
  34. 	for (int i = 1; i <= n; i++) {
  35. 		for (int j = 1; j <= m; j++) {
  36. 			if (s[i] == t[j]) {
  37. 				dp[i][j] = dp[i - 1][j - 1]; 
  38. 			}
  39. 			else {
  40. 				dp[i][j] = min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]}) + 1; 
  41. 			}
  42. 		}
  43. 	}
  44.  
  45. 	cout << dp[n][m] << '\n'; 
  46. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin 
LOVE
MOVIE
stdout 
2
https://ideone.com/KEyU6T
language:
C++14 (gcc 8.3)
created:
42 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!