51Nod 1183 编辑距离

编辑距离，又称Levenshtein距离（也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。 例如将kitten一字转成sitting： sitten （k->s） sittin （e->i） sitting （->g） 所以kitten和sitting的编辑距离是3。俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。 给出两个字符串a,b，求a和b的编辑距离。 Input 第1行：字符串a(a的长度 <= 1000)。 第2行：字符串b(b的长度 <= 1000)。 Output 输出a和b的编辑距离 Input示例 kitten sitting Output示例 3

分析：对于两个字符串a和b，dp[i][j]记录a的前i个字符转换到b的前j个字符的最小编辑距离。对于dp[0][i]和dp[i][0]，都等于i。

#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; char a[1005]; char b[1005]; int dp[1005][1005]; void solve() { for(int i=0;i<=1001;i++) { dp[i][0]=i; dp[0][i]=i; } int len1=strlen(a); int len2=strlen(b); for(int i=1;i<=len1;i++) { for(int j=1;j<=len2;j++) { if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]; else { dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1; } } } printf("%d\n",dp[len1][len2]); } int main() { scanf("%s",a); scanf("%s",b); solve(); return 0; }