编辑距离问题
#include<iostream>
#include<string>

using namespace std;

#define MAX 1001

int nEditD[MAX][MAX];

void vInit(int nA,int nB);
void vGetEdit(string sA,string sB,int nA,int nB);
void vOut(int nA,int nB);
int min(int nA,int nB);
int get3Min(int nA,int nB,int nC);
int nDiff(char cA,char cB);

int main()
{
int nCase;
int nX,nY;
int i;
string sX,sY;
cin>>nCase;
for(i=1;i<=nCase;i++)
{
cin>>sX>>sY;
sX=" "+sX;
sY=" "+sY;
nX=sX.size()-1;
nY=sY.size()-1;
vInit(nX,nY);
vGetEdit(sX,sY,nX,nY);
vOut(nX,nY);
}
return 0;
}

void vInit(int nA,int nB)
{
int i,j;

for(i=0;i<=nA;i++)
{
nEditD[i][0]=i;
}

for(j=1;j<=nB;j++)
{
nEditD[0][j]=j;
}
}

void vGetEdit(string sA,string sB,int nA,int nB)
{
int i,j;

for(i=1;i<=nA;i++)
{
for(j=1;j<=nB;j++)
{
nEditD[i][j]=get3Min(nEditD[i-1][j]+1,nEditD[i][j-1]+1,nEditD[i-1][j-1]+nDiff(sA[i],sB[j])); }
}
}

void vOut(int nA,int nB)
{
cout<<nEditD[nA][nB]<<endl;
}

int min(int nA,int nB)
{
return (nA<nB?nA:nB);
}

int get3Min(int nA,int nB,int nC)
{
return(min(min(nA,nB),nC));
}

int nDiff(char cA,char cB)
{
return((cA==cB)?0:1);
}