fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define MAX 5000
  6. int dp[MAX][MAX],op[MAX][MAX];
  7. string a,b;
  8.  
  9. int res(int m, int n)
  10. {
  11. 	if(dp[m][n] !=0)
  12. 	return dp[m][n];
  13.  
  14. 	if(m == 0)
  15. 	{
  16. 		return dp[m][n] = n;
  17. 	}
  18.  
  19. 	if(n == 0)
  20. 	{
  21. 		return dp[m][n] = m;
  22. 	}
  23.  
  24. 	if(a[m-1] == b[n-1])
  25. 	{
  26. 		return dp[m][n] = res(m-1,n-1);
  27. 	}
  28.  
  29.  
  30. 	return dp[m][n] = min(min(res(m,n-1),res(m-1,n)),res(m-1,n-1)) + 1;
  31. }
  32.  
  33. int main()
  34. {
  35. ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  36.  
  37. 	int t;
  38. 	cin>>t;
  39.  
  40. 	while(t--)
  41. 	{
  42. 		memset(dp,0,sizeof dp);
  43. 		cin>>a>>b;
  44. 		int m = a.length(), n = b.length();
  45. 		assert(m<=MAX and n<=MAX);
  46. 		cout<<res(m,n)<<endl;
  47. 	}
  48. }
  49.  
Success #stdin #stdout 0.03s 210560KB
comments (?)
stdin
copy 
1
FOOD
MONEY
stdout
copy 
4
https://ideone.com/cWS8gC
language:
C++14 (gcc 8.3)
created:
7 years 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!