最新字符串比较问题PPT课件.ppt

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

1、字符串比较问题字符串比较问题问题描述问题描述l设A和B是长度相同的2个字符串。A和B的距离距离定义为相应位置字符距离字符距离之和。2个非空格字符的距离距离是它们的ASCII码之差的绝对值。空格与空格的距离为0；空格与其它字符的距离为一定值k。l字符串A的扩展扩展是在A中插入若干空格字符所产生的字符串。在字符串A和B的所有长度相同的扩展中，有一对距离最小的扩展，该距离称为字符串A和B的扩展距扩展距离离。l对于给定的字符串A和B，试设计一个算法，计算其扩展距离。求解过程求解过程d00d01d02d03d04d05d10d11d12d13d14d15d20d21d22d23d24d25d30d31d

2、32d33d34d35d40d41d42d43d44d45d50d51d52d53d54d55计算最优值计算最优值l直接利用上述递归式很容易写出一个计算dij的递归算法l考虑到子问题的重叠性质，使用动态规划算法自底向上计算最优值能提高算法效率l算法的初步实现：直接使用二维数组来保存dij，通过一个二重循环来计算dmn算法的初步实现算法的初步实现l求一对字符的字符距离的函数CharDistancelunsigned long CharDistance(const char&x,const char&y)int tag=0;if(x=)tag+=1;if(y=)tag+=1;switch tag

3、case 0:return(abs(x-y);case 1:return k;case 2:return 0;l求两个字符串扩展距离的函数lunsigned long MinDistance(const string&A,const string&B,unsigned long*d)int i,j,s,t;s=0;t=0;d00=0;for(i=1;i=m;+i)di0=i*k;if(Ai-1=)di0-=(+s)*k;for(j=1;i=n;+j)d0j=j*k;if(Bj-1=)d0j-=(+t)*k;for(i=1;i=m;+i)for(j=1;j=n;+j)dij=di-1j-1+Ch

4、arDistance(Ai,Bj);if(t=di-1j+CharDistance(Ai,)dij)dij=t;if(t=dij-1+CharDistance(,Bj)dij)dij=t;return dmn;求解过程求解过程d00d01d02d03d04d05d10d11d12d13d14d15d20d21d22d23d24d25d30d31d32d33d34d35d40d41d42d43d44d45d50d51d52d53d54d55复杂度分析复杂度分析l以上算法的时间复杂度与空间复杂度均为O(mn)l通过观察以上计算过程，不难发现，在计算第i行元素dij时只涉及到di-1j-1,di-1j与dij-1。即只用到数组的第i-1行与第i行。l因此在算法中，若按照从上到下，从左到右的逐行计算过程，只需用两个一维数组保存当前行与上一行的数据即可，从而可将空间复杂度降为O(n)，进一步若考虑取min(m,n)为列数，则空间复杂度可减至O(minm,n)结束语结束语谢谢大家聆听！谢谢大家聆听！15