edit distance
http://www.spoj.com/problems/EDIST/





#include<iostream>
#include<stdio.h>
#include<bits/stdc++.h>

using namespace std;
int dp[2001][2001];
char a[400001],b[400001];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
long long int i,j,l1,l2;
//cout<<"enter first string "<<endl;
scanf("%s",a);

//cout<<"enter second string "<<endl;
scanf("%s",b);

//int dp[100][100];
l1=strlen(a);
l2=strlen(b);

 for(j=0;j<=l2;j++)
   {dp[0][j]=j; }

for(j=0;j<=l1;j++)
   {dp[j][0]=j;}

for(i=1;i<=l1;i++)
{
 for(j=1;j<=l2;j++)
 {
   if(a[i-1]==b[j-1])
   dp[i][j]=min(dp[i][j-1]+1,min(dp[i-1][j]+1,dp[i-1][j-1]));

   else
   dp[i][j]=min(dp[i][j-1]+1,min(dp[i-1][j]+1,dp[i-1][j-1]+1));;
 }

}

//cout<<dp[l1][l2];
cout<<dp[l1][l2]<<endl;
    }
return 0;
}