数据结构与算法----5.2 编辑距离

[c++]代码库

#include <iostream>
#include <string>
using namespace std;

int EditDistance(string x, string y)
{
	int i,j, m, n, *a, *b ;
	m=x.length();n=y.length();
	a=new int[n+1]; b=new int[n+1]; 
	for (j=0;j<=n;j++) b[j]=j; 
	for ( i=1; i<=m; i++) 
	{
		for (j=0;j<=n;j++) a[j]=b[j] ;
		b[0]=i;
		for (j=1; j<=n; j++) 
		{
			if (x[i-1]==y[j-1]) b[j]=a[j-1];
			else b[j]=a[j-1]+1;
			if (a[j]+1<b[j]) b[j]=a[j]+1;
			if (b[j-1]+1<b[j]) b[j]=b[j-1]+1;
		}
	}
	return b[n];
}
int main()
{
    string x="abcd";
	string y="aabc";
	cout<<"字符串x:"<<x<<endl<<"字符串y:"<<y;
	cout<<endl<<"x与y的编辑距离为："<<EditDistance(x,y)<<endl;	
	return 0;
}