2022年字符串比较问题分享 .pdf

《2022年字符串比较问题分享 .pdf》由会员分享，可在线阅读，更多相关《2022年字符串比较问题分享 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、字符串比较问题一、问题描述对于长度相同的2 个字符串A 和 B，其距离定义为相应位置字符距离之和。2 个非空格字符的距离是它们的ASCII码之差的绝对值。空格与空格的距离为0；空格与其它字符的距离为一定值 k。在一般情况下，字符串A 和 B 的长度不一定相同。字符串A 的扩展是在A 中插入若干 空格字符所产生的字符串。在字符串A 和 B 的所有长度相同的扩展中，有一对距离最小的 扩展，该距离称为字符串A 和 B 的扩展距离。对于给定的字符串A 和 B，试设计一个算法，计算其扩展距离。二、算法设计解答：设字符串 A 和 B的字串 A1.i 和 B1.j 的扩展距离是val(i,j)；依题意，字符

2、串 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)（使用动态规划算法，自底向上的计算各个子问题并利用每次计算的结

3、果，避免重复运算，从而降低算法复杂度。）名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 5 页 -从动态规划递归式可知，算法的时间复杂度为O（mn），m 和 n 分别是字符串 A 和 B 的长度。代码如下：#include#include#define MAX 100000/标识最大的可能整数int val300300;std:string stra;/字符串 Astd:string strb;/字符串 Bint k;/定值 k/返回字符 a 与 b 的 ASCII码的差的绝对值int dist(char a,char b)return abs(a-b);int comp()名师

4、资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 5 页 -int len1,len2;int tmp;val00=0;len1=stra.length();len2=strb.length();for(int i=0;i=len1;i+)/字符串 A 和 B的有效下标是o1len,下标 0 表示空字符串/i 或 j 是 0 表示 A 或 B 串为空串for(int j=0;j=len2;j+)if(i+j)/i 和 j 至少一个大于 0valij=MAX;tmp=vali-1j+k;if(i&(tmpvalij)/i 大于 0valij=tmp;名师资料总结-精品资料欢迎下载-名师精

5、心整理-第 3 页，共 5 页 -tmp=valij-1+k;if(j&(tmpvalij)/j 大于 0valij=tmp;tmp=vali-1j-1+dist(strai,strbj);if(i*j)&(tmpstrastrbk;名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 5 页 -stra=+stra;/此处在字符串开头添加一个空格，是为了使字符串strastrb=+strb;/的控制台输入的有效字符下标从 1到 stra.length()std:coutcomp()std:endl;system(pause);return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 5 页 -