editdistance.txt

用动态规划算法思想求最小编辑距离

#include <iostream.h>
#include <string.h>
#include <stdio.h>
int min(int a, int b)
{
	int t = a<b?a:b;
	
	return t;
		
}
 int minEditDistance(char *s1, char *s2 )
{
     
  int len1	=	strlen(s1);
  int len2	=	strlen(s2);
  int i,j;
  //int m[50][50];
  //int*   m   =   new   int[len1][len2];  
 //int m[0][0]   =   0;
  for   (i=0;   i<=len1;   i++)   m[i][0]   =   i;   
  for   (j=0;   j<=len2;   j++)   m[0][j]   =   j;   
    
  for    ( i=1;   i<=len1;   i++)   
     for   ( j=1;   j<=len2;   j++){ 
  
          int val   =   (s1[i]   ==   s2[j])   ?   0   :   1;   
          m[i][j]   =   min(   m[i-1][j-1]   +   val,   
                                        min(m[i-1][j]+1   ,   m[i][j-1]+1));   
      }  
      int result = m[len1][len2];

     //delete []m;

     return result;
}
void main()
{   
	char s1[50],s2[50];
    cout<<"请输入字符串A："<<endl;
	//printf("请输入字符串A：\n");
	scanf("%s",s1);
	//cin	 >>	s1	>>endl;
	cout<<"请输入字符串B："<<endl;
    //printf("请输入字符串B：\n");
    scanf("%s",s2);
	//cin	 >>	s2	>>endl;
   //printf("%d\n",minEditDistance(s1,s2));
	cout<<minEditDistance(s1,s2)<<endl;
}