PKU 3356-AGTC

問題概要

二つの文字列の編集距離を求めよ。複数ケースあるので注意

解法

編集距離をDPで求める。
詳しくはレーベンシュタイン距離 - Wikipediaを詳細。

実装(C++)

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int n,m;
int dp[1001][1001];
char x[1001],y[1001];

int main() {
	while(~scanf("%d%s%d%s",&n,x,&m,y)){
		memset(dp,0x7F,sizeof(dp));
		dp[0][0]=0;
		for(int i=0;i<=n;i++){
			dp[i][0]=i;
		}
		for(int j=0;j<=m;j++){
			dp[0][j]=j;
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				int cost=(x[i-1]!=y[j-1]);
				dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+cost));
			}
		}
		printf("%d\n",dp[n][m]);
	}
	return 0;
}