fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int N = 5e3 + 5; 
  11.  
  12. int n, m;  
  13. string s, t;  
  14. int dp[N][N]; 
  15.  
  16. int main() {
  17. 	ios::sync_with_stdio(0); cin.tie(0);  	
  18. 	cin >> s >> t;  
  19. 	n = s.size(), m = t.size();  
  20. 	s = ' ' + s;  
  21. 	t = ' ' + t;  
  22.  
  23.  
  24. 	for (int i = 0; i <= n; i++) {
  25. 		for (int j = 0; j <= m; j++) dp[i][j] = INF; 
  26. 	}
  27.  
  28. 	dp[0][0] = 0;   
  29. 	for (int j = 1; j <= m; j++) dp[0][j] = j;   
  30. 	for (int i = 1; i <= n; i++) dp[i][0] = i;   
  31.  
  32. 	for (int i = 1; i <= n; i++) {
  33. 		for (int j = 1; j <= m; j++) {
  34. 			if (s[i] == t[j]) {
  35. 				dp[i][j] = dp[i - 1][j - 1]; 
  36. 			}
  37. 			else {
  38. 				dp[i][j] = min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]}) + 1; 
  39. 			}
  40. 		}
  41. 	}
  42.  
  43. 	cout << dp[n][m] << '\n'; 
  44. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
LOVE
MOVIE
stdout
copy 
2
https://ideone.com/CoZVES
language:
C++14 (gcc 8.3)
created:
1 year 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!