126.编辑距离问题

2598 编辑距离问题

 

 时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 钻石 Diamond
 
题目描述 Description

设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括:

(1)删除一个字符;

(2)插入一个字符;

(3)将一个字符改为另一个字符。

将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离,记为d(A,B)。试编写程序,对任给的2个字符串A和B,计算出它们的编辑距离d(A,B)。

输入描述 Input Description

输入文件edit.in有两行,第一行是字符串A,第二行是字符串B。

输出描述 Output Description

输出文件edit.out只有一行,即编辑距离d(A,B)。

样例输入 Sample Input

fxpimu

xwrs

样例输出 Sample Output

5

数据范围及提示 Data Size & Hint

40%的数据字符串A、B的长度均不超过100;

100%的数据字符串A、B的长度均不超过4000。

分类标签 Tags 点此展开 

【算法分析】

w状态:f [ i][ j]记录a ib j的最优编辑距离
w结果:f[ m][ n],其中mn分别是ab的串长
w初值:b串空,要删a串长个字符;a串空,要插b串长个字符
w转移方程:当a[ i]=b[ j]时,f[ i][ j]=f[i-1][j-1],否则,
w              f[ i][ j]=min(f[i-1][j-1]+1,f[i][j-1]+1,f[i-1][j]+1)
w说明:f[i-1][j-1]+1:改a [i]b [j]
w    f[i][j-1]+1a [i]后插入b[j-1]
w    f[i-1][j]+1:删a [i]
代码:
#include< cstdio >
#include< iostream >
using namespace std;
#include< cstring >
#define INFn 4001
int f[INFn][INFn];
char a[INFn],b[INFn];
int lena,lenb;
int main()
{
scanf("%s",a+1);//读入a,b字符串 
scanf("%s",b+1);
lena=strlen(a+1);lenb=strlen(b+1);//求出a,b长度 
for(int i=1;i<=lena;++i)
f[i][0]=i;//DP的临界条件,要把a的前i位和b的前0位相同,那么要删除i个字符 
for(int i=1;i<=lenb;++i)
f[0][i]=i;//要把b的前i位和a的前0位相同,那么要给a加上i个字符,就是i步。 
for(int i=1;i<=lena;++i)//f数组里储存着使a的前i位与b的前j位相同的最小步骤 
 for(int j=1;j<=lenb;++j)
 if(a[i]==b[j]) f[i][j]=f[i-1][j-1];//如果当前这两个相同的话,那么步骤是0,和之前的一样 
 else f[i][j]=min(min(f[i-1][j-1],f[i][j-1]),f[i-1][j])+1;
 
cout<<f[lena][lenb]<<endl;
return 0;
 
原文地址:https://www.cnblogs.com/c1299401227/p/5370688.html