change.txt

C精彩编程百例源码

#include "stdafx.h"

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

int min(int x,int y,int z) 
{
							int min_three=((x)<=(y)?
						((x)<=(z)?(x):(z)):
						((y)<=(z)?(y):(z)));
return min_three;
}

float edit_sim(string a,string b)
{
	int i,j,count;
	int insert_b,delete_a,change;

	int m=a.length(),n=b.length();

    int **cost=new int*[m+1];
	  for(i=0;i<m+1;i++)
	  cost[i]=new int[n+1]; 
	  
	  cost[0][0]=0;
	  for(i=1;i<=m;i++)
		  cost[i][0]=cost[i-1][0]+1;
	  for(j=1;j<=n;j++)
		  cost[0][j]=cost[0][j-1]+1;

	  for(i=0;i<m;i++)
	  {  for(j=0;j<n;j++)
		  { if(a[i]==b[j])
				  cost[i+1][j+1]=cost[i][j];
			  else{
				  insert_b=cost[i+1][j]+1;
				  delete_a=cost[i][j+1]+1;
				  change=cost[i][j]+2;
				  cost[i+1][j+1]=min(insert_b,delete_a,change);
			  }
		  }
	  }
		
	  /*for(i=0;i<=m;i++)
		   for(j=0;j<=n;j++)
			   cout<<cost[i][j]<<endl;
	  
	  cout<<count<<endl;*/
	   count=cost[m][n];
	  float sim=(float)(m+n-count)/(m+n);
	  return sim;
}

 
int main(int argc, char* argv[])
{
	string a="abcdef",b="xbyzek";
	//cout<<min(4,5,6)<<endl;
	cout<<edit_sim(a,b)<<endl;
	return 0;
}