lcs算法.docx

程序员编程艺术第十一章：最长公共子序列(LCS)问题 0、前言 ??? 程序员编程艺术系列重新开始创作了（前十章，请参考 HYPERLINK /v_JULY_v/archive/2011/06/02/6460494.aspx \t _blank 程序员编程艺术第一~十章集锦与总结）。回顾之前的前十章，有些代码是值得商榷的，因当时的代码只顾阐述算法的原理或思想，所以，很多的与代码规范相关的问题都未能做到完美。日后，会着力修缮之。 ??? 搜遍网上，讲解这个LCS问题的文章不计其数，但大多给读者一种并不友好的感觉，稍感晦涩，且代码也不够清晰。本文力图避免此些情况。力保通俗，阐述详尽。同时，经典算法研究系列的第三章（ HYPERLINK /v_JULY_v/archive/2010/12/31/6110269.aspx \t _blank 三、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可以使用动态规划法解决。下文具体描述。 第二节、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的动态规划解法已叙述殆尽，不过，为了成书的某种必要性，下面，我试着再多加详细阐述这个问题。 第三节、动态规划算法解LCS问题 3.1、最长公共子序列的结构 ??? 最长公共子序列的结构有如下表示： ??? 设序列X=x1, x2, …, xm和Y=y1,