学步园

转自：http://www.cnblogs.com/grenet/archive/2011/03/11/1964417.html

在参阅《A Longest Common Subsequence Algorithm Suitable for Similar Text Strings》（Narao Nakatsu，Yahiko Kambayashi，Shuzo Yajima著）后。发现该算法可以利用线性空间求出最长公共子序列。该算法的时间占用O（n（m-p+1）），p为最长公共子序列的长度。

　　字符串A和字符串B，计算LCS(A,B)

　　定义一：设M=Len(A)，N=Len(B)，不妨设M≤N。

　　定义二：A=a₁a₂……a_M，表示A是由a₁a₂……a_M这M个字符组成

　　　　　　B=b₁b₂……b_N，表示B是由b₁b₂……b_N这N个字符组成

　　　　　　LCS(i,j)=LCS(a₁a₂……a_i,b₁b₂……b_j)，其中1≤i≤M，1≤j≤N

　　定义三：L(k,i)表示，所有与字符串a₁a₂……a_i有长度为k的LCS的字符串b₁b₂……b_j中j的最小值。

　　　　　　用公式表示就是：L(k,i)=Min｛j｝ Where LCS(i,j)=k

　　　　　　用一个例子来说明：A="CD"，B="CEFDRT"。

　　　　　　很明显的是LCS(2,1)=1，LCS(2,2)=1，LCS(2,3)=1。

　　　　　　满足LCS(2,j)=1这个条件的j有三个，分别是j=1、j=2、j=3。其中j最小值是1。故L(1,2)=1

　　为了推导L的计算，有下面几个定理。

　　定理一：任意的i，1≤i≤M。有L(1,i)＜L(2,i)＜L(3,i)……

　　定理二：任意的i，1≤i≤M-1。任意的k，1≤k≤M。有L(k,i+1)≤L(k,i)

　　定理三：任意的i，1≤i≤M-1。任意的k，1≤k≤M－1。有L(k,i)＜L(k+1,i+1)

　　定理四：如果L(k,i+1)存在，则L(k,i+1)的计算公式为

　　　　　　L(k,i+1)=Min｛Min｛j｝，L(k,i)｝ Where ｛a_i+1=b_j And j>L(k-1,i)｝

　　上面四个定理证明从略。可以从上面四个定理推导出L的计算。

　　故，L的计算公式为

　　　　①L(1,1)=Min｛j｝ Where ｛a₁=b_j｝

　　　　②L(1,i)=Min｛Min｛j｝ Where ｛a_i=b_j｝，L(1,i-1)｝ 　　此时，1<i≤M

　　　　③L(k,i)=Min｛Min｛j｝ Where ｛a_i=b_j  And j＞L(k-1,i-1)｝，L(k,i-1)｝ 　　此时，1<i≤M，1<k≤M

　　　　注：以上公式中，若找不到满足Where后面条件的j，则j=MaxValue

　　　　　　当i＜k时，则L(k,i)=MaxValue

　　　　　　MaxValue是一个常量，表示“不存在”

　　在实际的算法实现中，为了简化运算，再次提出几个定义。

　　定义：　　　　L(0,i)=0　　　　　　　　1≤i≤M

　　　　　　　　　L(k,0)=MaxValue　　　　1<k≤M

　　　　　　　　　MaxValue=N+1　　　　（只要定义一个j不可能取到的值就可以了）

　　　　则，在①中的公式可以写成

　　　　L(1,1)=Min｛j｝ Where ｛a₁=b_j｝=Min｛j｝ Where ｛a₁=b_j And j>0 }

　　　　　　　=Min｛Min｛j｝ Where ｛a₁=b_j And j>0 ｝，MaxValue｝

　　　　　　　=Min｛Min｛j｝ Where ｛a₁=b_j And j>L(0,0) ｝，L(1,0)｝

　　　　在②中的公式可以写成

　　　　L(1,i)=Min｛Min｛j｝ Where ｛a_i=b_j｝，L(1,i-1)｝

　　　　　　　=Min｛Min｛j｝ Where ｛a_i=b_j And j>0｝，L(1,i-1)｝

　　　　　　　=Min｛Min｛j｝ Where ｛a_i=b_j And j>L(0,i)｝，L(1,i-1)｝　　　　此时，1<i≤M

　　于是，三个公式统一了　　

　　④L(k,i)=Min｛Min｛j｝ Where ｛a_i=b_j  And j＞L(k-1,i-1)｝，L(k,i-1)｝ 　　此时，1≤i≤M，1≤k≤M

　　且当i＜k时，则L(k,i)=MaxValue

　　仔细观察④，公式还可以写成如下

　　⑤　　L(k,i)=Min｛j｝ Where ｛a_i=b_j  And L(k-1,i-1)<j<L(k,i-1)｝　1≤i≤M，1≤k≤M，且j存在　 　　

　　或　　L(k,i)=L(k,i-1)　　1≤i≤M，1≤k≤M，当j不存在时

　　写成⑤的目的有两个：一个是简化计算，不计算不必要的值；一个是为了标记，为后面计算最长公共子序列做准备。　　

　　接下来，将会用例子来说明：

　　A：481234781；B：4411327431

　　第一步：初始化L矩阵 

　　第二步：如表格所示，计算第一条对角线 

 　　　　运气很差，只有第一个单元格有值，其余的都是V（MaxValue），很显然这不是问题的解。这条对角线满足L(k-1,i-1)<j<L(k,i-1)的只有一个单元格。先把它标记出来。

　　第三步：如表格所示，计算相邻的第二条对角线 

L矩阵

		4	8	1	2	3	4	7	8	返回 【上篇】E-Form++跨平台移植的可行性研究 【下篇】不规则窗口 作者: synagogue 该日志由 synagogue 于11年前发表在综合分类下，最后更新于 2013年10月03日. 转载请注明: 线性空间求最长公共子序列的Nakatsu算法 | 学步园 +复制链接 抱歉!评论已关闭. 书签 招生 白云飘飘网 青岛房产网 最新文章New 网站优化可以收获更好的收益 robots在网页开发中起到了一定的 SEO引擎优化可以更好的方便搜索 Dreamweaver教程很实用，值得学习 很多的photoshop教程值得学习，你 编程语言很重要，特别是对于计算 数据库非常常见，也非常实用！ H5指的是第5代html，不同于传统企 HTML是什么，该怎么制作？ 本站推荐 为什么PHP的吉祥物是一头大象 作业的提交和监控（二） 作业的提交和监控（一） Boost – Function 分析 奇技淫巧 – C/C++ 宏自身 模板的 SFINAE 原则 Octopress 和 Git 的结合 Electric-fence 介绍 web前端 数据库 编程语言 搜索技术 关于本站 返回首页 Copyright © 2013-2018 学步园  保留所有权利. 软文销售 QQ客服：2265327166 （其他合作也可洽谈） 必威体育 必威电竞