文档介绍：所有的最长公共子序列( LCS ) 一、问题描述子序列的概念: 设X= <x 1,x 2,┅,x m>, 若有 1≤i 1 <i 2<┅<i k≤m,得 Z=< z 1,z 2,┅,z k> = <x i1,x i2,┅,x ik>, 则称 Z是X 的子序列,记为 Z<X 。 . X=<A,B,C,B,D,A,B>, Z=<B,C,B,A>, 则有 Z<X 。公共子序列的概念: 设X,Y 是两个序列,且有 Z<X 和 Z<Y ,则称 Z是X和Y 的公共列。最长公共子序列的概念: 若 Z<X , Z<Y , 且不存在比 Z 更长的 X和Y 的公共子序列, 则称 Z是X和Y 的最长公共子序列,记为 Z ? LCS(X , Y)。但是 LCS 不是只有一个, 最长公共子序列往往不止一个。 e .g. X=<A,B,C,B,D,A,B>, Y=<B,D,C,A,B,A>, 则 Z=<B,C,B,A>, Z’=<B,C,A,B>, Z ’’=<B,D,A,B> 均属于 LCS(X , Y) ,即 X,Y 有3个 LCS 。本文描述如何寻找所有的 LCS 二、问题分析①先描述寻找一个 LCS 的思想: 记X i=﹤x 1,…,x i ﹥即 X 序列的前 i 个字符(1≤i≤ m) (前缀) Y j=﹤y 1,…,y j ﹥即 Y 序列的前 j 个字符(1≤j≤ n) (前缀) 假定 Z= ﹤z 1,…,z k﹥∈ LCS(X , Y)。若x m =y n (最后一个字符相同) ,则不难用反证法证明: 该字符必是 X与Y的任一最长公共子序列 Z( 设长度为 k) 的最后一个字符,即有 z k=x m=y n。且显然有 Z k-1∈ LCS(X m-1 ,Y n-1)即Z的前缀 Z k-1是X m-1 与Y n-1 的最长公共子序列。若x m≠y n ,则亦不难用反证法证明: 要么 Z∈ LCS(X m-1 , Y), 要么 Z∈ LCS(X ,Y n-1)。由于 z k≠x m与z k≠y n 其中至少有一个必成立,因此:若 z k≠x m 则有 Z∈ LCS(X m-1 , Y),若 z k≠y n 则有 Z∈ LCS(X ,Y n-1)。∴若x m =y n, 则问题化归成求 X m-1 与Y n-1的 LCS ,( LCS(X , Y) 的长度等于 LCS(X m-1 ,Y n-1) 的长度加 1) 若x m≠y n, 则问题化归成求 X m-1 与Y的 LCS 及X与Y n-1的 LCS LCS(X , Y) 的长度为: Max {LCS(X m-1 , Y) 的长度, LCS(X ,Y n-1) 的长度}求 LCS(X m-1 , Y) 的长度与 LCS(X ,Y n-1) 的长度这两个问题不是相互独立的: ∵两者都需要求 LCS(X m-1 ,Y n-1) 的长度, 因而具有重叠性。此外, 两个序列的 LCS 中包含了两个序列的前缀的 LCS , 故问题具有最优子结构性质?考虑用动态规划法。引进一个二维数组 C, 用 C[i,j] 记录 X i与Y j的 LCS 的长度。如果我们是按行、列的序号从小到大地进行递推计算, (从第 1 行开始计算: C[1,1]、 C[1,2]、。。。 C[1,n], 再算 C[2,1]、 C[2,2]、。。。 C[