editdistance.cpp

来自「Editdistance是算法导论中经典的问题了。本代码以special的风格表」· C++ 代码 · 共 200 行

#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;

#define right 0      // 0
#define del 2         // 1
#define insert 3      // 2
#define replace 4      // 3

struct value{
	int result;
	int num;
};

struct transport{
	int sum;
	int* t;
};

value min(int x, int y, int z)
{
	value val;
	if(x < y)
	{
		val.result = x;
		val.num = 3;
	}
	else
	{
		val.result = y;
		val.num = 2;
	}

	if(val.result > z)
	{
		val.result = z;
		val.num = 1;
	}

	return val;
}


transport EditDistance(char a[], int n, char b[], int m)
{
	int* p = new int[(n+1)*(m+1)];
	transport tran;
	tran.t = new int[(n+1)*(m+1)];
	value val;
	int k = 0;
	int j = 0;
	for(; j < m+1; j++)
	{
		p[j] = j * insert;
		tran.t[j] = 2;
	}

	int i = 1;
	for(; i < n+1; i++)
	{
		p[i * (m+1)] = i * del;
		tran.t[i * (m+1)] = 1;
	}
	for(i = 1; i < n+1; i++)
		for(j = 1; j < m+1; j++)
		{
			k = a[i-1] == b[j-1] ? 0 : replace;
			val = min( p[(i-1)*(m+1)+(j-1)] + k, p[i*(m+1)+j-1] + insert,
				p[(i-1)*(m+1)+j] + del);
			p[i*(m+1)+j] = val.result;
			if(k == 0 && val.num == 3)
				tran.t[i*(m+1)+j] = 0;
			else
				tran.t[i*(m+1)+j] = val.num;
		}
	tran.sum = p[n*(m+1)+m];
	delete []p;
	return tran;
}


void Print(char a[], int n, char b[], int m, int t[])
{
	int i = n,j = m;
	stack<int> s;
	int num;
	while(!(i == 0 && j == 0))
	{
		num = t[i*(m+1)+j];
		s.push(num);
		switch(num)
		{
		case 0:
			i--;
			j--;
			break;
		case 1:
			i--;
			break;
		case 2:
			j--;
			break;

		case 3:
			i--;
			j--;
			break;
		}
	}

	i = 0;
	j = 0;
	int first,end;
	int count = 0;
	while(!s.empty())
	{
		num = s.top();
		s.pop();
		switch(num)
		{
		case 0:

			i++;
			j++;
			cout<<count<<"  right  ";
			break;
		case 1:
			j++;
			cout<<count<<"  delete  ";
			break;
		case 2:
			i++;
			cout<<count<<"  insert   ";
			break;
		case 3:
			i++;
			j++;
			cout<<count<<"  replace  ";
			break;
		}
		for(first=0; first < i; first++)
			cout<<b[first];
		cout<<"**";
		for(end = j; end < n; end++)
			cout<<a[end];
		cout<<endl;
		count++;
	}
	cout<<endl;
	cout<<"***********************************End*******************************";
	cout<<endl;
}
int main()
{
	int res;
	cout<<"Please input the length of first string:";
	cin>>res;
	char c = getchar();
	char* x = new char[res+1];
	cout<<"The first string x：";
	for (int i = 0; i < res; i++)
	{
		x[i] = getchar();
	}
	x[i] = '\0';
	c = getchar();
	//gets(x);
	int des;
	cout<<"Please input the length of second string:";
	cin>>des;
	c = getchar();
	char* y = new char[des+1];
	cout<<"The second string：";
	for(i = 0; i < des; i++)

	{
		y[i] = getchar();
	}
	y[i] = '\0';
	c = getchar();

	transport tran;
	tran = EditDistance(x, res, y, des);
	int n = tran.sum;
	cout<<endl<<endl<<endl;
	cout<<"Sring x：";
	puts(x);

	cout<<"String y：";
	puts(y);

	cout<<"Editditance is："<<n<<endl;
	cout<<endl<<endl<<endl;
	Print(x, res, y, des, tran.t);
	delete []x;
	delete []y;
	return 0;
}