首页 > 代码库 > openjudge-NOI 2.6-2988 计算字符串距离

openjudge-NOI 2.6-2988 计算字符串距离

题目链接:http://noi.openjudge.cn/ch0206/2988/

题解:

  首先,题目有误,少了一个添加操作

  和求解LCS之类的思路类似

  f[i][j]表示a序列中1..i的部分和b序列中1...j的部分的编辑距离,得:

  (1)i==0,j==0时,f[i][j]=0;

  (2)i==0,j>0时,f[i][j]=j;j==0,i>0时,f[i][j]=i;即需要对空串进行i或j个添加操作;

  (3)否则,f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]+check(i,j));(check函数:ai==bj返回1否则0)

    <1>默认a[1...i-1]和b[1...j]已经处理好时,只需要在ai-1后添加一个bj使a[1...i]与b[1...j]相同

    <2>默认a[1...i]和b[1...j-1]已经处理好时,只需要在bj-1后添加一个ai使a[1...i]与b[1...j]相同

    <3>默认a[1...i-1]和b[1...j-1]已经处理好时,如果ai==bj,即不需要进行操作,否则需要对ai或者bj进行一次修改操作,使a[1...i]与b[1...j]相同

 1 #include<cstdio>
 2 #include<cstring>
 3 #define MAXN 1010
 4 int lena,lenb,f[MAXN][MAXN];
 5 char a[MAXN],b[MAXN];
 6 inline int min(int x,int y)
 7 {
 8     return x<y?x:y;
 9 }
10 bool check(int x,int y)
11 {
12     return a[x]==b[y]?true:false;
13 }
14 int main()
15 {
16     int T;
17     scanf("%d\n",&T);
18     while(T--)
19     {
20         memset(f,0,sizeof(f));
21         scanf("%s%s",a+1,b+1);
22         lena=strlen(a+1);lenb=strlen(b+1);
23         for(int i=1;i<=lena;++i)f[i][0]=i;
24         for(int i=1;i<=lenb;++i)f[0][i]=i;
25         f[0][0]=0;
26         for(int i=1;i<=lena;++i)
27         {
28             for(int j=1;j<=lenb;++j)
29             {
30                 f[i][j]=min(min(f[i-1][j],f[i][j-1])+1,f[i-1][j-1]+!(check(i,j)));
31             }
32         }
33         printf("%d\n",f[lena][lenb]);
34     }
35     return 0;
36 }

 

openjudge-NOI 2.6-2988 计算字符串距离