- 浏览: 426382 次
- 性别:
- 来自: 成都
文章分类
最新评论
-
binghc:
能使用浏览器作为客户端么,用socket构建一个最简单的htt ...
HTTPS那些事 用java实现HTTPS工作原理 -
littleShyBoy:
如果是使用http client请求https的接口,http ...
HTTPS那些事 用java实现HTTPS工作原理 -
skw1975:
...
HTTPS那些事 用java实现HTTPS工作原理 -
sealinesu:
看了半天,真的是半天,总算是把这些概念都理清了,谢谢博主
spring事务传播机制实例讲解 -
wanghaozdw:
请问下,在内外层事务均是REQUIRED的情况下,内层事务抛出 ...
spring事务传播机制实例讲解
程序员编程艺术系列重新开始创作了(前十章,请参考程序员编程艺术第一~十章集锦与总结)。回顾之前的前十章,有些代码是值得商榷的,因当时的代码只顾阐述算法的原理或思想,所以,很多的与代码规范相关的问题都未能做到完美。日后,会着力修善之。 搜遍网上,讲解这个LCS问题的文章不计其数,但大多给读者一种并不友好的感觉,稍感晦涩,且代码也不够清晰。本文力图避免此些情况。力保通俗,阐述详尽。同时,经典算法研究系列的第三章(三、dynamic programming)也论述了此LCS问题。有任何问题,欢迎不吝赐教。 什么是最长公共子序列呢?好比一个数列 S,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则S 称为已知序列的最长公共子序列。 举个例子,如:有两条随机序列,如 1 3 4 5 5 ,and 2 4 5 5 7 6,则它们的最长公共子序列便是:4 5 5。 注意最长公共子串(Longest CommonSubstring)和最长公共子序列(LongestCommon Subsequence, LCS)的区别:子串(Substring)是串的一个连续的部分,子序列(Subsequence)则是从不改变序列的顺序,而从序列中去掉任意的元素而获得的新序列;更简略地说,前者(子串)的字符的位置必须连续,后者(子序列LCS)则不必。比如字符串acdfg同akdfc的最长公共子串为df,而他们的最长公共子序列是adf。LCS可以使用动态规划法解决。下文具体描述。 解最长公共子序列问题时最容易想到的算法是穷举搜索法,即对X的每一个子序列,检查它是否也是Y的子序列,从而确定它是否为X和Y的公共子序列,并且在检查过程中选出最长的公共子序列。X和Y的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的一个子序列相应于下标序列{1, 2, …, m}的一个子序列,因此,X共有2m个不同子序列(Y亦如此,如为2^n),从而穷举搜索法需要指数时间(2^m * 2^n)。 事实上,最长公共子序列问题也有最优子结构性质。 记: Xi=﹤x1,⋯,xi﹥即X序列的前i个字符 (1≤i≤m)(前缀) Yj=﹤y1,⋯,yj﹥即Y序列的前j个字符 (1≤j≤n)(前缀) 假定Z=﹤z1,⋯,zk﹥∈LCS(X , Y)。 若xm=yn(最后一个字符相同),则不难用反证法证明:该字符必是X与Y的任一最长公共子序列Z(设长度为k)的最后一个字符,即有zk = xm = yn 且显然有Zk-1∈LCS(Xm-1 , Yn-1)即Z的前缀Zk-1是Xm-1与Yn-1的最长公共子序列。此时,问题化归成求Xm-1与Yn-1的LCS(LCS(X , Y)的长度等于LCS(Xm-1 , Yn-1)的长度加1)。 若xm≠yn,则亦不难用反证法证明:要么Z∈LCS(Xm-1, Y),要么Z∈LCS(X , Yn-1)。由于zk≠xm与zk≠yn其中至少有一个必成立,若zk≠xm则有Z∈LCS(Xm-1 , Y),类似的,若zk≠yn 则有Z∈LCS(X , Yn-1)。此时,问题化归成求Xm-1与Y的LCS及X与Yn-1的LCS。LCS(X , Y)的长度为:max{LCS(Xm-1 , Y)的长度, LCS(X , Yn-1)的长度}。 由于上述当xm≠yn的情况中,求LCS(Xm-1 , Y)的长度与LCS(X , Yn-1)的长度,这两个问题不是相互独立的:两者都需要求LCS(Xm-1,Yn-1)的长度。另外两个序列的LCS中包含了两个序列的前缀的LCS,故问题具有最优子结构性质考虑用动态规划法。 也就是说,解决这个LCS问题,你要求三个方面的东西:1、LCS(Xm-1,Yn-1)+1;2、LCS(Xm-1,Y),LCS(X,Yn-1);3、max{LCS(Xm-1,Y),LCS(X,Yn-1)}。 行文至此,其实对这个LCS的动态规划解法已叙述殆尽,不过,为了成书的某种必要性,下面,我试着再多加详细阐述这个问题。 3.1、最长公共子序列的结构 最长公共子序列的结构有如下表示: 设序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的一个最长公共子序列Z=<z1, z2, …, zk>,则: 其中Xm-1=<x1, x2, …, xm-1>,Yn-1=<y1, y2, …, yn-1>,Zk-1=<z1, z2, …, zk-1>。 由最长公共子序列问题的最优子结构性质可知,要找出X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的最长公共子序列,可按以下方式递归地进行:当xm=yn时,找出Xm-1和Yn-1的最长公共子序列,然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时,必须解两个子问题,即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。 由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如,在计算X和Y的最长公共子序列时,可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题,即计算Xm-1和Yn-1的最长公共子序列。 与矩阵连乘积最优计算次序问题类似,我们来建立子问题的最优值的递归关系。用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=<x1, x2, …, xi>,Yj=<y1, y2, …, yj>。当i=0或j=0时,空序列是Xi和Yj的最长公共子序列,故c[i,j]=0。其他情况下,由定理可建立递归关系如下: 直接利用上节节末的递归式,我们将很容易就能写出一个计算c[i,j]的递归算法,但其计算时间是随输入长度指数增长的。由于在所考虑的子问题空间中,总共只有θ(m*n)个不同的子问题,因此,用动态规划算法自底向上地计算最优值能提高算法的效率。 计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与Yj的最长公共子序列的长度,b[i,j]记录指示c[i,j]的值是由哪一个子问题的解达到的,这在构造最长公共子序列时要用到。最后,X和Y的最长公共子序列的长度记录于c[m,n]中。 由算法LCS_LENGTH计算得到的数组b可用于快速构造序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的最长公共子序列。首先从b[m,n]开始,沿着其中的箭头所指的方向在数组b中搜索。 这种方法是按照反序来找LCS的每一个元素的。由于每个数组单元的计算耗费Ο(1)时间,算法LCS_LENGTH耗时Ο(mn)。 下面的算法LCS(b,X,i,j)实现根据b的内容打印出Xi与Yj的最长公共子序列。通过算法的调用LCS(b,X,length[X],length[Y]),便可打印出序列X和Y的最长公共子序列。 在算法LCS中,每一次的递归调用使i或j减1,因此算法的计算时间为O(m+n)。 例如,设所给的两个序列为X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>。由算法LCS_LENGTH和LCS计算出的结果如下图所示: 我来说明下此图(参考算法导论)。在序列X={A,B,C,B,D,A,B}和 Y={B,D,C,A,B,A}上,由LCS_LENGTH计算出的表c和b。第i行和第j列中的方块包含了c[i,j]的值以及指向b[i,j]的箭头。在c[7,6]的项4,表的右下角为X和Y的一个LCS<B,C,B,A>的长度。对于i,j>0,项c[i,j]仅依赖于是否有xi=yi,及项c[i-1,j]和c[i,j-1]的值,这几个项都在c[i,j]之前计算。为了重构一个LCS的元素,从右下角开始跟踪b[i,j]的箭头即可,这条路径标示为阴影,这条路径上的每一个“↖”对应于一个使xi=yi为一个LCS的成员的项(高亮标示)。 所以根据上述图所示的结果,程序将最终输出:“B C B A”。 对于一个具体问题,按照一般的算法设计策略设计出的算法,往往在算法的时间和空间需求上还可以改进。这种改进,通常是利用具体问题的一些特殊性。 例如,在算法LCS_LENGTH和LCS中,可进一步将数组b省去。事实上,数组元素c[i,j]的值仅由c[i-1,j-1],c[i-1,j]和c[i,j-1]三个值之一确定,而数组元素b[i,j]也只是用来指示c[i,j]究竟由哪个值确定。因此,在算法LCS中,我们可以不借助于数组b而借助于数组c本身临时判断c[i,j]的值是由c[i-1,j-1],c[i-1,j]和c[i,j-1]中哪一个数值元素所确定,代价是Ο(1)时间。既然b对于算法LCS不是必要的,那么算法LCS_LENGTH便不必保存它。这一来,可节省θ(mn)的空间,而LCS_LENGTH和LCS所需要的时间分别仍然是Ο(mn)和Ο(m+n)。不过,由于数组c仍需要Ο(mn)的空间,因此这里所作的改进,只是在空间复杂性的常数因子上的改进。 另外,如果只需要计算最长公共子序列的长度,则算法的空间需求还可大大减少。事实上,在计算c[i,j]时,只用到数组c的第i行和第i-1行。因此,只要用2行的数组空间就可以计算出最长公共子序列的长度。更进一步的分析还可将空间需求减至min(m, n)。 动态规划的一个计算最长公共子序列的方法如下,以两个序列 X、Y 为例子: 设有二维数组 f[i][j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有: 其中,same(a,b)当 X 的第 a 位与 Y 的第 b 位完全相同时为“1”,否则为“0”。 此时,f[i][j]中最大的数便是 X 和 Y 的最长公共子序列的长度,依据该数组回溯,便可找出最长公共子序列。 该算法的空间、时间复杂度均为O(n2),经过优化后,空间复杂度可为O(n),时间复杂度为O(nlogn)。 以下是此算法的java代码: 下面咱们来了解一种不同于动态规划法的一种新的求解最长公共子序列问题的方法,该算法主要是把求解公共字符串问题转化为求解矩阵L(p,m)的问题,在利用定理求解矩阵的元素过程中(1)while(i<k),L(k,i)=null, 求出每列元素,一直到发现第p+1 行都为null 时退出循环,得出矩阵L(k,m)后,B[L(1,m-p+1)]B[L(2,m-p+2)]…B[L(p,m)]即为A 和B 的LCS,其中p 为LCS 的长度。 6.1 主要定义及定理 矩阵中元素L(k,i)=Li(k),这里(1<i<=m,1<k<=m),null 表示L(k,i)不存在。当i<k 时,显然L(k,i)不存在。 6.2 算法思想 下面给出一个例子来说明:给定字符串A 和B,A=acdabbc,B=cddbacaba,(m= A =7,n= B =9)。按照定理给出的递推公式,求出A 和B 的L 矩阵如图2,其中的$表示NULL。 则A 和B 的LCS 为B[1]B[2]B[4]B[6]=cdbc,LCS 的长度为4。 6.3 算法伪代码 6.4 结语 若有任何问题,恳请不吝指正。谢谢各位。完。本文转自csdn
0、前言
第一节、问题描述
第二节、LCS问题的解决思路
穷举法
第三节、动态规划算法解LCS问题
3、2.子问题的递归结构
3、3.计算最优值
3、4.构造最长公共子序列
3、5.算法的改进
第四节、编码实现LCS问题
第五节、改进的算法
(2)while(L(k,i)=k),L(k,i+1)=L(k,i+2)=…L(k,m)=k;
定理1 ∀ i∈[1,m],有Li(l)<Li(2)<Li(3)<…<Li(m) .
定理2 ∀i∈[l,m-1],∀k∈[l,m],有i 1 L + (k)<= i L (k).
定理3 ∀ i∈[l,m-1], ∀ k∈[l,m-l],有i L (k)< i 1 L + (k+l).
以上三个定理都不考虑Li(k)无定义的情况。
定理4[3] i 1 L + (k)如果存在,那么它的取值必为: i 1 L + (k)=Min(j, i L (k))。这里j 是满足以下条件的最小整数:A[i+l]=B[j]且j> i L (k-1)。
设p=Maxk(L(k , m) ≠ null) , 可以证明L 矩阵中L(p,m) 所在的对角线,L(1,m-p+1),L(2,m-p+2)…L(p-1,m-1),L(p,m) 所对应的子序列B[L(1,m-p+1)]B[L(2,m-p+2)]…B[L(p,m)]即为A 和B 的LCS,p 为该LCS 的长度。这样,LCS 问题的求解就转化为对m m L × 矩阵的求解。
根据定理,第一步求出第一行元素,L(1,1),L(1,2),…L(1,m),第二步求第二行,一直到发现第p+1 行都为null 为止。在计算过程中遇到i<k 时,L(k,i)=null, 及L(k,i)=k时,L(k,i+1)=L(k,i+2)=…L(k,m)=k。这样,计算每行的时间复杂度为O(n),则整个时间复杂度为O(pn)。在求L 矩阵的过程中不用存储整个矩阵,只需存储当前行和上一行即可。空间复杂度为O(m+n)。
算法 L(A,B,L)
输入 长度分别为m,n 的字符串A,B
输出 A,B 的最长公共子序列LCS
本节主要描述区别于动态规划法的一种新的求解最长公共子序列问题的方法,在不影响精确度的前提下,提高序列匹配的速度,根据定理i 1 L + (k)=Min(j, i L (k))得出矩阵,在求解矩阵的过程中对最耗时的L(p,m)进行条件约束优化。我们在Intel(R) Core(TM)2 Quad 双核处理器、1G 内存,软件环境:windows xp 下试验结果证明,本文算法与其他经典的比对算法相比,不但能够取得准确的结果,而且速度有了较大的提高(本节参考了刘佳梅女士的论文)。
发表评论
-
使用位运算实现加法
2014-04-23 16:32 920转自CSDN (原文地址 http://blog.csdn. ... -
排序算法之快速排序
2014-04-11 13:24 745本文转自CSDN http://blog ... -
使用位运算实现加法
2013-03-13 16:37 710位运算 实现加法 分类: Algorithm2 ... -
总结交换2个数的值不用临时变量的方法
2012-11-23 11:14 3529今天温习了一下java基础,看到2个数的交换方法的时候,想到 ... -
算法导论学习之第七章-快速排序
2012-10-31 16:20 758快速排序是对冒泡排序的一种改进。它的基本思想是:通 ... -
算法导论学习之第二章-寻找逆序对
2012-10-26 23:51 1384今天学习算法导论第二章中提到的逆序对问题,思前想后采 ...
相关推荐
而LCS则不同,它不要求连续性,所以 "AE" 也是 "ABCDEF" 和 "ABEFGH" 的一个最长公共子序列,尽管它不是公共子串。 接下来,我们将从算法的角度探讨如何求解LCS。一种常见的方法是使用动态规划,这在计算机科学中是...
总之,PHP实现求解最长公共子串问题的方法主要依赖于动态规划算法,通过构建和利用二维数组来逐步求解问题,并最终通过回溯找到最长公共子串。这种算法不仅在理论上具有严谨性,而且在实际应用中也表现出了较高的...
本文将详细介绍如何利用C语言实现最大公共子串(Longest Common Substring,简称 LCS)的计算方法。最大公共子串问题是指在两个或多个字符串中找到最长的相同子串。本算法采用动态规划的方式解决这一问题,并通过一...
一、问题描述 子串应该比较好理解,至于什么是子序列,这里给出一个例子...在上述例子的中,最长公共子序列为blog(cnblogs, belong),最长公共子串为lo(cnblogs, belong)。 二、求解算法 对于母串X=<x1,x2,⋯,xm
最长公共子序列(Longest Common Subsequence,LCS)是计算机科学中一种经典的字符串处理问题,广泛应用于数据挖掘、文本比较、生物信息学等领域。它指的是在不考虑字符顺序的情况下,两个或多个字符串共有的最长的...
它通过构建一个二维数组,记录两序列中任意子串的LCS长度,从而逐步求解整个序列的LCS。 **C语言实现** 是指用C编程语言编写代码来解决这个问题。C语言是一种底层、高效的语言,适合处理这样的算法问题。通常,LCS...
在两个给定的字符串中,LCS是指无需考虑字符顺序的最长子串,它同时存在于这两个字符串中。这个问题在文本编辑、生物信息学、软件工程等领域都有广泛的应用。 动态规划是解决LCS问题的一种高效方法,因为它避免了...
最长公共子序列(Longest Common Subsequence,简称LCS)是计算机科学中一种经典的问题,主要涉及字符串处理和动态规划。在本问题中,我们关注的是如何通过递归算法来解决这个问题。递归是一种解决问题的方法,它将...
**最长公共子序列(LCS, Longest ...总结,LCS算法是解决字符串比对问题的一种基础工具,通过动态规划或记忆化搜索的方式高效求解最长公共子序列。在实际应用中,LCS算法被广泛应用于文本分析、生物信息学等多个领域。
题目:如果字符串一的所有字符按其在字符串...分析:求最长公共子序列(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,因此一些重视算法的公司像MicroStrategy都把它当作面试题。 完整介绍动态规划将
针对求解两个字符串的最长公共子串问题,如Spoj的LCS题目,我们可以采用以下策略: 1. **构造母串的后缀自动机**:首先,以其中一个字符串(母串A)为基础,构建后缀自动机。 2. **逐位扫描匹配串**:随后,逐字符...
此外,还有一个相似的问题是最长公共子串(Longest Common Substring,简称LCSs),与LCS的区别在于子串必须是连续的。在示例代码中,同样是通过动态规划求解,但当发现子串时,记录最大长度`rst`并清零当前位置的`...
在编程领域,字符串操作是常见任务之一,而求解两个字符串的最长公共子序列(Longest Common Subsequence, LCS)是字符串处理中的一个重要问题。这个问题涉及到动态规划算法,它能有效地解决这类具有最优子结构和...
最长公共子序列问题与最长公共子串类似,不同的是,子序列不要求连续,而子串要求连续。动态规划同样适用于这个问题的解决。 17. 最长递增子序列(LIS) 最长递增子序列问题是在一个数组中找到最长的严格递增的子...
常见的字符串处理包括查找、替换、连接、插入和删除等基本操作,而更深入的算法如最长公共子序列(LCS)和最长公共子串(LIS)则是研究字符串相似性的基础。字符串相似度度量算法如Levenshtein距离提供了一种衡量两个...
最长公共子序列(Longest Common Subsequence,LCS)问题是计算机科学中一个经典的字符串处理问题,它寻找两个序列之间的最长子序列,这个子序列不必连续但必须保持原序列的相对顺序。在本例中,提供的文件是使用C++...
最长公共子串(Longest Common Substring,LCS)与LCS不同,它要求子串在原序列中是连续的。这个问题也可以用动态规划解决,构建一个`dp[i][j]`表示字符串A的前i个字符和B的前j个字符的最长公共子串的长度。状态转移...