【例9.20】编辑距离
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 249 通过数: 65
【题目描述】
设A和B是两个字符串。我们要用最少的字符操作次数,将字符串A转换为字符串B。这里所说的字符操作共有三种:
1、删除一个字符;
2、插入一个字符;
3、将一个字符改为另一个字符。
对任意的两个字符串A和B,计算出将字符串A变换为字符串B所用的最少字符操作次数。
【输入】
第一行为字符串A;第二行为字符串B;字符串A和B的长度均小于200。
【输出】
只有一个正整数,为最少字符操作次数。
【输入样例】
sfdqxbw
gfdgw
【输出样例】
4
【来源】
No
算法分析:
设f[i][j]为编辑a[i].b[j]最短距离。
边界条件:
1. 当b[j]为0时,需要将a[i]全部删除。
2. 当a[i]为0时,需要将b[j]全部插入a[i]当中
状态转移方程:
If(a[i]==b[j]) f[i][j]=f[i-1][j-1]; //不需要改变
else f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1;
说明:
Sf[i][j-1]+1 在a[i]后插入b[j-1]
f[i-1][j]+1 删除a[i]
f[i-1][j-1]+1 将a[i]改为b[j]
比如要计算cafe和coffee的编辑距离。cafe→caffe→coffe→coffee
先创建一个6×8的表(cafe长度为4,coffee长度为6,各加2)
(1):
c |
o |
f |
f |
e |
e |
c |
|||||
a |
|||||
f |
|||||
e |
表 |
1 |
接着,在如下位置填入数字(表2):
c |
o |
f |
f |
e |
e |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
c |
1 |
|||||
a |
2 |
|||||
f |
3 |
|||||
e |
4 |
表 |
2 |
从3,3格开始,开始计算。取以下三个值的最小值:
· 如果最上方的字符等于最左方的字符,则为左上方的数字。否则为左上方的数字+1。(对于3,3来说为0)
· 左方数字+1(对于3,3格来说为2)
· 上方数字+1(对于3,3格来说为2)
因此为格3,3为0(表3)
c |
o |
f |
f |
e |
e |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
c |
1 |
0 |
||||
a |
2 |
|||||
f |
3 |
|||||
e |
4 |
循环操作,推出下表
c |
o |
f |
f |
e |
e |
||
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
c |
1 |
0 |
1 |
2 |
3 |
4 |
5 |
a |
2 |
1 |
1 |
2 |
3 |
4 |
5 |
f |
3 |
2 |
2 |
1 |
2 |
3 |
4 |
e |
4 |
3 |
3 |
2 |
2 |
2 |
3 |
取右下角,得编辑距离为3。
实现代码:
#include<bits/stdc++.h>
using namespace std;
int i,j,la,lb,f[202][202];
char a[202],b[202];
int main()
{cin>>a>>b;la=strlen(a);lb=strlen(b);for(i=1;i<=la;i++)f[i][0]=i;for(i=1;i<=lb;i++)f[0][i]=i;for(i=1;i<=la;i++)for(j=1;j<=lb;j++){if(a[i-1]==b[j-1])f[i][j]=f[i-1][j-1];elsef[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1;}cout<<f[la][lb];return 0;}