编辑距离问题

编辑距离问题

时间： 1ms        内存：64M

描述：

设A和B是2 个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的2个字符串A和B，计算出它们的编辑距离d(A,B)。对于给定的字符串A和字符串B，计算其编辑距离d(A,B)。

输入：

输入数据的第一行是字符串A，第二行是字符串B。

输出：

输出只有一行，一个整数表示编辑距离d(A,B)。

示例输入：

fxpimu
xwrs

示例输出：

5

提示：

参考答案（内存最优[1096]）：

#include<stdio.h>
#include<string.h>
int jie(int a,int b,int c,char yi,char er)
{
    int shang=c+1,xia=b+1,zuo=a;
    if(yi!=er)
        zuo++;
    if(shang<=xia&&shang<=zuo)
        return shang;
    if(xia<=shang&&xia<=zuo)
        return xia;
    if(zuo<=shang&&zuo<=xia)
        return zuo;
}
int main()
{
    int a[10304],d[10034],i,j,k;
    char b[10304],c[10034],*p,*q;
    scanf("%s",&b);
    scanf("%s",&c);
    {
    p=b;
    q=c;
	a[0]=0;
    for(i=1;*(q+i-1)!='\0';i++)
    {
        a[i]=i;
    }
    for(i=0;*(p+i)!='\0';i++)
    {
        d[0]=i+1;
        for(j=0;*(q+j)!='\0';j++)
        {
            d[j+1]=jie(a[j],a[j+1],d[j],*(p+i),*(q+j));
        }
		a[0]=i+1;
        for(k=1;*(q+k-1)!='\0';k++)
        {
            a[k]=d[k];
        }
    }
    printf("%d\n",a[j]);
    }
}

参考答案（时间最优[20]）：

#include<iostream>
#include<string>
#include <malloc.h>
using namespace std;
int min_val(const int a,const int b,const int c)
{
    int min = a<b?a:b;
    min = min<c?min:c;
    return min;
}
int edit_distance(const string &str1,const string &str2)
{
    int m=(int)str1.length(),n=(int)str2.length(),i,j,cost;
    if(m==0)return n;
    if(n==0)return m;
    int **dp=(int **)malloc((m+1)*sizeof(int*));
    for(i=0; i<=m; ++i)dp[i]=(int *)malloc((n+1)*sizeof(int));
    for(i=0; i<=m; ++i)dp[i][0] = i;
    for(j=1; j<=n; ++j)dp[0][j] = j;
    for(i=1; i<=m; ++i)
        for(j=1; j<=n; ++j)
        {
            cost = (str1[i-1]==str2[j-1]?0:1);
            dp[i][j] = min_val(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+cost);
        }
    cost = dp[m][n];
    for(i=0; i<=m; ++i)delete dp[i];
    delete dp;
    return cost;
}
int main()
{
    string str1,str2;
   cin>>str1>>str2;
    cout<<edit_distance(str1,str2)<<endl;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。