问题:
对于长度相同的2个字符串A和B,其距离定义为相应位置字符距离之和。2个非空格字符的距离是它们的ASCII码之差的绝对值;空格与空格的距离为0,空格与其他字符的距离为一个定值k。在一般情况下,字符串A和B的长度不一定相同。字符串A的扩展是在A中插入若干空格字符所产生的字符串。在字符串A和B的所有长度相同的扩展中,有一对距离最短的扩展,该距离称为字符串A和B的扩展距离。对于给定的字符串A和B,设计一个算法,计算其扩展距离。
测试数据:
输入:cmc snmn 2 (分别表示字符串A、B和定值k)
输出:10
解答:
设字符串A和B的字串A[1...i]和B[1...j]的扩展距离是val(i, j);
依题意,字符串A和B有三种可能的情况:
1)A串最后一个字符是空格,B串最后一个字符是字母,则val(i, j) = val(i-1, j) + k;
2)A串最后一个字符时字母,B串最后一个字符时空格,则val(i, j) = val(i, j-1) + k;
3)A串和B串最后一个字符均是字母,则val(i, j) = val(i-1, j-1) + dist(ai , bi);
由上可知,val(i, j)具有最优子结构性质,且满足如下递推式:
val(i, j) = min{ val(i-1, j) + k,val(i, j) + k,val(i-1, j-1) + dist(ai , bi) }
(使用动态规划算法,自底向上的计算各个子问题并利用每次计算的结果,避免重复运算,从而降低算法复杂度。)
从动态规划递归式可知,算法的时间复杂度为O(mn),m和n分别是字符串A和B的长度。
代码如下:
#include <iostream>
#include <cmath>
#define MAX 100000 //标识最大的可能整数
int val[300][300];
std::string stra; //字符串A
std::string strb; //字符串B
int k; //定值k
//返回字符a与b的ASCII码的差的绝对值
int dist(char a, char b)
{
return abs(a-b);
}
int comp()
{
int len1, len2;
int tmp;
val[0][0] = 0;
len1 = stra.length();
len2 = strb.length();
for(int i=0; i<=len1; i++) //字符串A和B的有效下标是º1~len,下标0表示空字符串
{ //i或j是0表示A或B串为空串
for(int j=0; j<=len2; j++)
{
if(i+j)//i和j至少一个大于0
{
val[i][j] = MAX;
tmp = val[i-1][j] + k;
if(i && (tmp<val[i][j]))//i大于0
val[i][j] = tmp;
tmp = val[i][j-1]+k;
if(j && (tmp<val[i][j]))//j大于0
val[i][j] = tmp;
tmp = val[i-1][j-1] + dist(stra[i], strb[j]);
if((i*j) && (tmp<val[i][j])) //i和j至少有一个不为0
val[i][j] = tmp;
}
}
}
return val[len1][len2];
}
int main()
{
std::cin>>stra>>strb>>k;
stra = " " + stra; //此处在字符串开头添加一个空格,是为了使字符串stra
strb = " " + strb; //的控制台输入的有效字符下标从1到stra.length()
std::cout<<comp()<<std::endl;
system("pause");
return 0;
}
分享到:
相关推荐
《动态规划》之--字符串比较问题(扩展距离),主要思路通过策略和无效性来求解。特点最优子结构性质,重叠子问题。
题目描述:对于长度相同的2个字符串A和B,其距离定义为相应位置字符距离之和。2个非空格字符的距离是它们的ASCII码之...在字符串A和B的所有长度相同的扩展中,有一对距离最短的扩展,该距离称为字符串A和B的扩展距离。
字符串比较问题 Description ?问题描述: 对于长度相同的2 个字符串A和B,其距离定义为相应位置字符距离之和。2 个非空格 字符的距离是它们的ASCII码之差的绝对值。空格与空格的距离为0;空格与其它字符的距 离...
对于给定的字符串A和B,给定其字串的内容和空格相对字符的距离,使用动态规划算法求解两字符串的扩展距离。
距离的计算:如果A1是字符串A的扩展串,B1是字符串B的扩展串,A1与B1具有相同的长度,那么定义字符串A1与B1的距离为相应位置上的字符的距离总和,而两个非空格字符的距离定义为它们的ASCII码的差的绝对值,而空格...
如果A1是字符串A的扩展串,B1是字符串B的扩展串,A1与B1具有相同的长度,那么定义字符串A1与B1的距离为相应位置上的字符的距离总和,而两个非空格字符的距离定义为它们的ASCII码的差的绝对值,而空格字符与其它任意...
在字符串A和B的所有长度相同的扩展中,有一对距离最小的扩展,该距离称为字符串A和B的扩展距离。算法要求如下1、 数据输入:第1行是字符串A,第2行是字符串B,第
目前,已有许多高效的字符串相似性连接算法被提出,但是这些算法在过滤的过程中利用的往往是字符串本身的局部信息,而忽略了字符串集合的整体信息,故性能没有得到充分的提高。为此,提出了一种基于划分的算法Part-...
内容简介安装文档许可证历史记录源代码作者简介Levenshtein Python C扩展模块包含用于快速计算Levensh的功能内容简介安装文档许可证历史记录源代码作者简介Levenshtein Python C扩展模块包含用于快速计算Levenshtein...
C和Ruby实现都支持任何类型的字符串编码,例如UTF-8,EUC-JP,Big5等。安装gem install jaro_winkler用法require 'jaro_winkler'# Jaro Winkler DistanceJaroWinkler . distance "MARTHA" , "MARHTA"# => 0.9611...
varchar2 1~4000字节 可变长度字符串,与CHAR类型相比,使用VARCHAR2可以节省磁盘空间,但查询效率没有char类型高 数值类型 Number(m,n) m(1~38) n(-84~127) 可以存储正数、负数、零、定点数和精度为38位的浮点数...
该项目旨在构建一个Python软件包,该软件包由一组全面且可扩展的字符串标记器(例如字母标记器,空格标记器)和字符串相似性度量(例如编辑距离,Jaccard,TF / IDF)组成。 该软件包是免费的,开源的并且是BSD许可...
LEVENSHTEIN(s1, s2)函数返回将一个字符串转换为另一个字符串所需的添加,替换和删除操作的数量。 LEVENSHTEIN_RATIO(s1, s2)函数以百分比形式返回两个字符串的相似性( 0 <= x <= 100 )。 它们的工作方式与...
使得串口设备能够立即具备TCP/IP网络接口功能,连接网络进行数据通信,极大的扩展串口设备的通信距离。 完全支持Windows全系列(包含嵌入式)操作系统,如:WinXP/Win2K3/Win7/WinCE.NET/Poceket PC/Windows Mobile...
为了克服该方法耗时长、计算量大的缺点, 采用一种符号化算法, 用扩展符号聚集近似对序列符号化表示, 再对字符串进行距离度量, 并以太湖流域小梅口站逐日水位数据为例进行验证。实验表明该方法的挖掘结果更全面, 运算...
开发人员可能希望利用此libray或人为的字符串比较扩展方法中包含的一种或多种算法,如下所示: bool isEqual = input . FuzzyEquals ( name ); double coefficient = input . FuzzyMatch ( name ); 包含的算法 ...
算法分析实验,字符串扩展距离问题。算出最优距离。
使得串口设备能够立即具备TCP/IP网络接口功能,连接网络进行数据通信,极大的扩展串口设备的通信距离。 对于RS232接口,一台串口设备只能够接一台PC机,如果需要连接多台PC机,原来的串口方案将不易于扩展,而网络则...
在字符串A和B的所有长度相同的扩展中,有一对距离最小的扩展,该距离称为字符串A和B的扩展距离。依题意,字符串A和B有三种可能的情况:1)A串最后一个字符是空格,
-Window的Target属性由字符串类型变为枚举类型,注意更新以前的代码:Target="_self" -> Target="Self", Target="_parent" -> Target="Parent"。 -MenuButton, LinkButton, Button, LinkButtonField的...