算法LCS-所有的最长公共子序列23页.doc

所有的最长公共子序列（LCS）一、 问题描述子序列的概念： 设X = ，若有1i1i2 ikm，得Z= = ，则称Z是X的子序列，记为ZX。e.g. X=, Z=, 则有ZX。公共子序列的概念：设X，Y是两个序列，且有ZX和ZY，则称Z是X和Y 的公共列。最长公共子序列的概念：若ZX，ZY，且不存在比Z更长的X和Y 的公共子序列，则称Z是X和Y 的最长公共子序列，记为ZLCS(X , Y)。但是LCS不是只有一个，最长公共子序列往往不止一个。e.g. X=, Y=, 则Z=, Z=, Z=均属于LCS(X , Y) ，即X,Y有3个LCS。本文描述如何寻找所有的LCS二、问题分析先描述寻找一个LCS的思想：