编辑距离问题

编辑距离问题

时间: 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;
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注