首页 > 代码库 > SDUT 1225-编辑距离(串型dp)

SDUT 1225-编辑距离(串型dp)

2024-07-28 22:27:29   221人阅读

编辑距离

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

假设字符串的基本操作仅为：删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。 
我们把进行了一次上述三种操作的任意一种操作称为进行了一步字符基本操作。
下面我们定义两个字符串的编辑距离：对于两个字符串a和b，通过上述的基本操作，我们可以把a变成b或b变成a，那么字符串a变成字符串b需要的最少基本字符操作步数称为字符串a和字符串b的编辑距离。
例如：a="ABC",b="CBCD",则a与b的编辑距离为2。
你的任务就是：编一个快速的程序来计算任意两个字符串的编辑距离。

输入

输入包含多组测试数据。每组测试数据一行，为字符串A和字符串B。
字符串的长度不大于1024，且全为字母。

输出

编辑距离。

示例输入

ABC CBCD

示例输出

2
一开始想爆搜，一看范围傻了。。。串模型DP。
设dp[i][j]代表原始串从1到i位置上与目标串从1到j位置上的最短编辑距离，
dp[i][j]=min(dp[i][j-1]+1(删除a[i]),dp[i-1][j]+1(增加b[j]),a[i]==b[j]?dp[i-1][j-1]:dp[i-1][j-1]+1);
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <list>
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
int dp[1025][1025];
char a[1025],b[1025];
int My_min(int x,int y,int z)
{
	return min(min(x,y),z);
}
int main()
{
	while(~scanf("%s%s",a,b))
	{
		int lena=strlen(a),lenb=strlen(b);
		for(int i=0;i<=lenb;i++)
			dp[0][i]=i;
		for(int i=0;i<=lena;i++)
			dp[i][0]=i;
		for(int i=1;i<=lena;i++)
			for(int j=1;j<=lenb;j++)
			dp[i][j]=My_min(dp[i-1][j]+1,dp[i][j-1]+1,a[i-1]==b[j-1]?dp[i-1][j-1]:dp[i-1][j-1]+1);
		printf("%d\n",dp[lena][lenb]);
	}
	return 0;
}

SDUT 1225-编辑距离(串型dp)


联系
我们