1. 题目

传送门= ̄ω ̄=

2. 题解

我记得我一年前在考试中推出了递推式。。。
可是我现在居然不会做了/(ㄒoㄒ)/~~
为什么我的智力可以下降的如此迅速。。。

首先,不难发现a到b的编辑距离=b到a的编辑距离

设$f(i,j)$为A的前i个字符到B的前j个字符的编辑距离。
递推式:
$f(i,j)=max(f(i,j-1),f(i-1,j),f(i-1,j-1))+1 (A[i]!=B[j])$
$f(i,j)=f(i-1,j-1) (A[i]==B[j])$
$f(i,0)=f(0,i)=i$

代码:

#include <bits/stdc++.h>
using namespace std;
char s1[2005],s2[2005];
int l1,l2,f[2005][2005];
int main()
{
    scanf("%s",s1+1),scanf("%s",s2+1),l1=strlen(s1+1),l2=strlen(s2+1);
    for(int i=1;i<2005;i++)f[0][i]=f[i][0]=i;
    for(int i=1;i<=l1;i++)
        for(int j=1;j<=l2;j++)
            if(s1[i]==s2[j])f[i][j]=f[i-1][j-1];
            else f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1;
    printf("%d\n",f[l1][l2]);
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

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

你是机器人吗? =。= *