sdutoj1225--编辑距离(dp:字符串转换)
转换 -- 字符串 编辑 DP 距离
2023-09-11 14:21:01 时间
编辑距离
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
提示
来源
ZJGSU
由a串变为b串,三种操作,写成二维的dp后,dp[i][j]代表a串匹配到i,b串匹配到j时一共须要的步数。
假设s1[i] == s2[j]那么直接能够从 dp[i-1][j-1]得到。或是dp[i-1][j]+1代表加入一个字符,dp[i][j-1]+1代表删除一个字符中得到
假设不同样。那么和上面同样,仅仅须要变化为dp[i-1][j-1]+1代表改动一个字符。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char s1[1200] , s2[1200] ;
int dp[1200][1200] ;
int main()
{
int i , j , l1 , l2 ;
while(scanf("%s %s", s1, s2)!=EOF)
{
memset(dp,0,sizeof(dp));
l1 = strlen(s1) ;
l2 = strlen(s2) ;
for(i = 0 ; i <= l1 ; i++)
dp[i][0] = i ;
for(j = 0 ; j <= l2 ; j++)
dp[0][j] = j ;
for(i = 1 ; i <= l1 ; i++)
{
for(j = 1 ; j <= l2 ; j++)
{
if( s1[i-1] == s2[j-1] )
dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j]+1,dp[i][j-1]+1) );
else
dp[i][j] = min(dp[i-1][j-1]+1,min(dp[i-1][j]+1,dp[i][j-1]+1) ) ;
}
}
printf("%d\n", dp[l1][l2]);
}
return 0;
}
#include <cstring>
#include <algorithm>
using namespace std;
char s1[1200] , s2[1200] ;
int dp[1200][1200] ;
int main()
{
int i , j , l1 , l2 ;
while(scanf("%s %s", s1, s2)!=EOF)
{
memset(dp,0,sizeof(dp));
l1 = strlen(s1) ;
l2 = strlen(s2) ;
for(i = 0 ; i <= l1 ; i++)
dp[i][0] = i ;
for(j = 0 ; j <= l2 ; j++)
dp[0][j] = j ;
for(i = 1 ; i <= l1 ; i++)
{
for(j = 1 ; j <= l2 ; j++)
{
if( s1[i-1] == s2[j-1] )
dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j]+1,dp[i][j-1]+1) );
else
dp[i][j] = min(dp[i-1][j-1]+1,min(dp[i-1][j]+1,dp[i][j-1]+1) ) ;
}
}
printf("%d\n", dp[l1][l2]);
}
return 0;
}
版权声明:本文博客原创文章,博客,未经同意,不得转载。
相关文章
- delphi -- 进制转换 函数表
- Java IO--字节-字符流转换OutputStreamWriter/InputStreamReader
- 倍福TwinCAT(贝福Beckhoff)基础教程2.2 TwinCAT常见类型使用和转换_字符串
- iOS开发笔记--UIView中的坐标转换
- Java实现 蓝桥杯VIP 基础练习 时间转换
- 日历工具类(一)——公历农历互相转换
- ObjextARX-VS2005-字符串转换
- LIBSVM使用实验兼数据转换--UCI-SPECTF
- Open3D(C++) 角度制与弧度制的相互转换
- Android GIS开发系列-- 入门季(7) 利用GeometryEngine坐标转换、计算距离与面积等
- Android GIS开发系列-- 入门季(8) Json与Geometry的相互转换
- 如何在JavaScript中将十进制转换为十六进制
- 配置seetaface+转换为dll+c#运用
- 转换流--OutputStreamWriter类与InputStreamReader类
- 13.3 time--时间操作和转换功能
- Gopher协议原理和限制介绍——Gopher协议支持发出GET、POST请求(类似协议转换):可以先截获get请求包和post请求包,在构成符合gopher协议的请求
- Jackson转换json大写_关于jackson转化json的原理_jackson序列化和反序列化Json
- 计算机基础--进制之间的转换