若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1723: 编辑距离问题

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,288

题目描述

设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

参考代码

#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)!='';i++)
    {
        a[i]=i;
    }
    for(i=0;*(p+i)!='';i++)
    {
        d[0]=i+1;
        for(j=0;*(q+j)!='';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)!='';k++)
        {
            a[k]=d[k];
        }
    }
    printf("%dn",a[j]);
    }
}

解析

暂无

hustoj

发表评论 取消回复

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

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Dreams孤独患者 原站点 Skip
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist