http://www.spoj.com/problems/EDIST/
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<string> using namespace std; int f[2002][2002]; char a[2002], b[2002]; int main(){ int t; scanf("%d", &t); while (t--){ memset(f, 127 / 3, sizeof(f)); scanf("%s%s", a, b); int n = strlen(a), m = strlen(b); for (int i = 0; i < n; i++) f[i][0] = i;/ for (int i = 0; i < m; i++) f[0][i] = i;/ for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++){ if (a[i-1] == b[j-1]) f[i][j] = f[i-1][j-1]; else f[i][j] = min(min(f[i-1][j], f[i][j-1]), f[i-1][j-1]) + 1; } printf("%d\n", f[n][m]); } return 0; }