摘要

本篇博文提供了实现求解所有最长公共子序列的程序实现，并提供输出所有公共子序列的方法解释，需要具备基础知识是求解一个公共子序列的动态规划方法，请自行查阅相关资料。

题目重述

子序列概念：设X=< x1, x2,┅, xm>，若有1≤i1< i2< ┅ = < xi1, xi2,┅, xik>，则称Z是X的子序列，记为Z

例如： X= , Z= , 则有Z

公共子序列概念：设X,Y是两个序列，则有Z

最长公共子序列：若Z Z?LCS(X , Y)。

问题: 最长公共子序列一般可以有多个，求解并输出所有的LCS。

问题分析

求解一个LCS比较容易，但求解所有的LCS比较繁琐，为了实现题目要求，程序引入了栈（Stack）存储结构用于存储具有两个方向的节点（i，j坐标），以及输出序列的存储数组，可实现了所有LCS的求解输出。

算法思想

a) 本题根据二维数组C，记录Xi，Yj的LCS长度，然后根据矩阵B记录“?”，“←”，“↑”，“←↑”四种情况，分别用整型数 3,-1,1,2表示，以便于记录；

b) 根据B矩阵求解LCS序列的规则，可以发现所有LCS路径构成了一个有向图，所以可以结合深度优先搜索算法并加以改进实现输出所有LCS；

c) 引入Stack（堆栈）存储结构（见程序 StackNode S[N];），S为结构体，包含i，j,pos三个参数，分别表示点的坐标，以及即将存入lcs的位置；同时分配动态数组（char*lcs =(char*)new char[len];）用于存储符合要求的数组；设置变量li用于记录要存入lcs数组的位置；

d) 算法核心即当遇到“←↑”情形，将B[i][j]=1，并将节点信息存入栈， 然后继续搜索下一个节点，当符合要求后输出序列，并回溯到最近的“←↑”节点（已经置为“↑”），并进行下一个序列的搜索输出，具体代码参见程序函数：void fn_OutputLCSes(int(*)[],char*,int(*)[],int, int)。

程序代码

/*-----------------------------------------------------------------
*                       输出所有LCSes 
* -----------------------------------------------------------------
*  By gujinjin    
*  求解任意两个序列的所有最长公共子序列（LCS）
*  Execute successfully on Visual Studio 2012 
*/
#include 
  
   

using std::cout;
using std::cin;
using std::endl;
// 定义数组最大长度
#define N 20

struct StackNode
{
	int i;
	int j;
	int pos;
};

/*-----------------------------------------------------------------
*                bool fn_Input(char*, int,char*,int)
* -----------------------------------------------------------------
*/
bool fn_Input(char* la, int na,char* lb,int nb)
{
	// Reutrn false
	if(na==0 || nb==0)return false;
	// Input list
	cout<<"Input La List:"<
   
    >la[i]; } cout<<"Input Lb List:"<
    
     >lb[j]; } return true; } /*----------------------------------------------------------------- * void fn_LCS(char*,char*,int(*)[],int, int) * ----------------------------------------------------------------- * Mb中 1表示上箭头，-1表示右箭头,2表示上、右箭头，3表示斜箭头 */ void fn_LCS(char* la,char* lb,int (*MC)[N],int (*Mb)[N],int na, int nb) { for(int i=0;i<=na;i++)MC[i][0]=0; for(int j=1;j<=nb;j++)MC[0][j]=0; for(int i=1;i<=na;i++) { for(int j=1;j<=nb;j++) { /* la,lb 是字母序列，从0开始而不是1 */ if(int(la[i-1]) == int(lb[j-1])) { MC[i][j]= MC[i-1][j-1]+1; Mb[i][j]=3; } else if(MC[i-1][j] > MC[i][j-1]) { MC[i][j] = MC[i-1][j]; Mb[i][j] = 1; } else if(MC[i-1][j] < MC[i][j-1]) { MC[i][j] = MC[i][j-1]; Mb[i][j] = -1; } else { MC[i][j] = MC[i][j-1]; Mb[i][j] = 2; } } // end of for j } // end of for i } /*----------------------------------------------------------------- * void fn_OutputPreInfo(char*,char*,int(*[],int(*)[],int,int) * ----------------------------------------------------------------- */ void fn_OutputPreInfo(char* la, char* lb,int(*MC)[N],int(*Mb)[N],int na,int nb) { cout<<"La序列元素个数"<
     
      =0 && j>=0) { if(Mb[i][j]==2) { Push(S,top,i,j,li); Mb[i][j]=1; i=i; j=j-1; } else if(Mb[i][j]==-1) { //Mb[i][j]=0; i=i; j=j-1; } else if(Mb[i][j]==1) { //Mb[i][j]=0; i=i-1; j=j; } else if(Mb[i][j]==3) { lcs[li]=la[i-1]; i=i-1; j=j-1; if(li==0) { for(int k=0;k
      
       >na>>nb; // 判断输入是否正确 if(fn_Input(la,na,lb,nb)) { // 获取MC，Mb辅助矩阵 fn_LCS(la,lb,MC,Mb,na,nb); // 输出矩阵信息 fn_OutputPreInfo(la,lb,MC,Mb,na,nb); // 输出 LCS cout<<"The LCSes are:"<
       
        
 
        
 
        
运行结果
 
        
求解 X=
         
          , Y=
          
           ，结果如下（控制台应用程序）：
          
         
 
        
结果为： 
         
          ，
          
           ，