最长公共子序列
前面有很多人问了最长公共子串的问题 ，但这个不是最长公共子串，而是最长公共子序列。
问题差别在于：子串必须是连续的，但子序列不必。
如:ABCBDAB和BDCABA最长公共子串只能是AB或BD，但最长公共子串是BCBA。
输入两个序列，求最长公共子序列。谢谢!
[解决办法]
【供参考】
一、算法思想
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子序列就是求给定两个序列的一个最长公共子序列。动态规划可以有效的解决此问题。由最长公共子序列问题的子序列的最优子结构性质，可以建立子问题最优的递归关系。用c[i][j]记录序列Xi和Yi的最长公共子序列的长度，递归关系如下：
0 i=0,j=0
c[i][j]= c[i-1][j][j-1]+1 i,j> 0;xi==yj
max c[i][j-1],c[i-1][j] I,j> 0;xi==yj
在具体的算法设计中，以序列X= { x1,x2,x3,…,xm }和Y= {y1,y2,y3,…,ym}作为输入。输出三个数组c,b,temp。其中c[i][j]存储Xi和Yj的公共子序列的长度，b[i][j]记录c[i][j]的值是由哪一个子问题的解得到的，这在构造最长公共子序列时要用到。问题得最优解，即X和Y得最长公共子序列记录在temp[h]中。
二、源代码
下面是在Microsoft Visual C++ 6.0中编写的求最长公共子序列的源程序，程序定义了最大得字符串长度为99，是将p48页的动态规划算法改写而来的。
#include <iostream.h>
#include <iomanip.h>
#define MAX 99
//typedef char MM;
void main()
{ int i,j,m,n,h=0;
char x[MAX]={ ' ', ' '},y[MAX]={ ' ', ' '},b[MAX][MAX]={ ' '};
int c[MAX][MAX]={0};
char temp[MAX]={ ' '};
cout < < "**本程序可以求得字符数在99以内的任意两个字符串的最大公共子序列**\n ";
cout < < "请输入第一个字符串的长度m= ";
cin> > m;
cout < < "请输入第一个字符串(“回车”结束)\n如果输入的字符数超过m,则会出错!\nx[ " < <m < < "]= ";
for(i=1;i <=m;i++)
cin> > x[i]; //键盘输入x和y
cout < < "请输入第二个字符串的长度n= ";
cin> > n;
cout < < "请输入第二个字符串\ny[ " < <n < < "]= ";
for(i=1;i <=n;i++)
cin> > y[i];
for(i=1;i <=m;i++)c[i][0]=0; //动态规划开始
for(i=1;i <=n;i++)c[0][i]=0;
for(i=1;i <=m;i++)
for(j=1;j <=n;j++)
{if(x[i]==y[j])
{c[i][j]=c[i-1][j-1]+1;
b[i][j]= '\\ ';
}else
if(c[i-1][j]> =c[i][j-1])
{ c[i][j]=c[i-1][j];
b[i][j]= '│ ';
}else{c[i][j]=c[i][j-1];
b[i][j]= '- ';
}
} //动态规划结束
cout < < "c[m][n]中的内容：\n ";
for(i=0;i <=m;i++)
{for(j=0;j <=n;j++)
cout < <c[i][j];
cout < <endl;
}
cout < < "b[m][n]中的内容：\n ";
for(i=1;i <=m;i++)
{for(j=1;j <=n;j++)
cout < <b[i][j];
cout < <endl;
}
i=m,j=n;
while(1)
{if(i==0││j==0) break;
if(b[i][j]== '\\ '){
temp[h++]=x[i]; //反序记录最长公共子序列到temp中
i=i-1,j=j-1;
}
else
if(b[i][j]== '│ ')
i=i-1;
else
j=j-1;}
cout < < "\nx[ " < <m < < "]和y[ " < <n < < "]的最长公共子序列为： ";
for(i=h-1;i> =0;i--) //格式化输出最长公共子序列
if(i==h-1)
if(h==1)
cout < < "LCS: < " < <temp[i] < < "> ";
else
cout < < "LCS: < " < <temp[i];
else
if(i==0)
cout < < ", " < <temp[i] < < "> ";
else
cout < < ", " < <temp[i];
cout < < "\n " < <endl;
}
三、运算结果
其实它的最长公共子序列不止一个，这里只输出了其中的一个。
四、总结分析
在这个具体的算法中，还有可以改进的地方，比如在具体的求最大公共子序列中，可以不必要MAX的宏定义，只需将各数组设为具体的长度就可以节约不少的空间，大大降低程序的空间复杂度，但是为了键盘输入任意字符串，牺牲了很多的内存空间。在键盘输入字符串时，可以不用循环赋值，直接用cin> > x;cin> > y;这样就可以将这部分的时间复杂度从O(m+n)降到O(2)，但有一个相关的问题没解决，所以我没这样赋值。程序总的时间复杂度为：O(mn+3m+3n).
[解决办法]
最长公共子序列算法实现的其他参考：
http://www.soudie.net/top_56708_cat_20/
http://www.pudn.com/downloads11/sourcecode/others/detail44472.html
[解决办法]
一楼的好强啊，每次都在第一时间给出第一参考。
[解决办法]
大部分的算法教材里面都有详尽的解释的。一楼正解，个人认为动态规划算法最高效，但是如果不好懂的话也可以采取逐步进行扫描的方式。
[解决办法]
//楼上都是牛人，偶也帖一个动态规划方法的程序。
#include <iostream>
const int NUM_X = 8; //定义x序列的长度为常量
const int NUM_Y = 7; //定义y序列的长度为常量
int c[NUM_X+1][NUM_Y+1]; //c[i][j]保存(xi,yj)的最长子序列长度
int b[NUM_X][NUM_Y]; //简化最优解的构造
//=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
//计算LCS长度的函数
//=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
template <typename T>
void LcsLength(const T x[NUM_X], const T y[NUM_Y])
{
int m = NUM_X;
int n = NUM_Y;
//如果i=0,或j=0时c[i][j]=0
for(int i=1; i <= m; ++i)
c[i][0] = 0;
for(int j=0; j <= n; ++j)
c[0][j] = 0;
for(int i=1; i <= m; ++i)
{
for(int j=1; j <= n; ++j)
{
if(x[i-1] == y[j-1])
{
c[i][j] = c[i-1][j-1] +1;
b[i-1][j-1] = 1;
}
else if( c[i-1][j] > = c[i][j-1] )
{
c[i][j] = c[i-1][j];
b[i-1][j-1] = 2;
}
else
{
c[i][j] = c[i][j-1];
b[i-1][j-1] = 3;
}
}
}
}
template <typename T>
void PrintLcs(const T x[NUM_X], int i, int j) //递归调用输出
{
if( i==0 || j==0)
return;
if( b[i-1][j-1] == 1 )
{
PrintLcs(x, i-1, j-1);
std::cout < < " " < <x[i-1] < < " ";
}
else if( b[i-1][j-1] == 2 )
PrintLcs(x, i-1, j);
else
PrintLcs(x, i, j-1);
}
void main()
{
char x[NUM_X] = { 'a ', 'b ', 'd ', 'c ', 'b ', 'c ', 'b ', 'b ' };
char y[NUM_Y] = { 'a ', 'd ', 'a ', 'c ', 'b ', 'c ', 'b ' };
//测试一
LcsLength <char> (x, y);
PrintLcs <char> (x, NUM_X, NUM_Y); //输出最长子序列
//测试二
//int ix[NUM_X] = {1, 0, 0, 1, 0, 1, 0, 1};
//int iy[NUM_Y] = {0, 1, 0, 1, 1, 0, 1, 1, 0};
//LcsLength <int> (ix, iy);
//PrintLcs <int> (ix, NUM_X, NUM_Y);
}
