首先，说明一下子序列的定义……
一个序列A=｛a1,a2,a3,...,an｝，从中删除任意若干项，剩余的序列叫A的一个子序列。
很明显（并不明显……），子序列……并不需要元素是连续的……（一开始的时候思维总是以为元素是连续的，好傻啊……）
然后是公共子序列……
如果C是A的子序列，也是B的子序列，那么C是A和B的公共子序列……
公共子序列一般不止一个，最长的那个就是最长公共子序列，当然也可能不止一个……
煮个栗子……
A=｛1，3，6，9，5，4，8，7｝，B=｛1，6，3，4，5，7｝
｛1，4，7｝是A和B的公共子序列
｛1，3，4，7｝是A和B的最长公共子序列
好了，说明的部分就到这，接下来，进入解决问题的部分……
给出序列A=｛a1,a2,a3...an｝，B=｛b1,b2,b3...bn｝
我们用lcs[i][j]来表示A的前i项和B的前j项的最长公共子序列的长度
flag[i][j]表示这一点是由哪点继承来的，然后，开始搜索……
如果……
(1)A[i]==B[j]
那么就代表lcs[i][j]的最后一项一定是A[i]，就是在lcs[i-1][j-1]接上A[i],也就是lcs[i][j]=lcs[i-1][j-1]+1，并记录flag[i][j]
(2)A[i]!=B[j]
那么lcs[i][j]=max(lcs[i-1][j-1],lcs[i][j-1])，因为既然接不上，那就继承一个长一点的留着呗，不要忘记了flag[i][j]的数字是不同的亲~
可能我说的比较简略，上一张比较好理解的图……
可能第一次看会很凌乱，仔细看吧亲……
最后按flag打出来就好了~
最后上代码
#include<stdio.h>
#include<string.h>
int lcs[][];
int flag[][];
char a[],b[];
void findlcs(char a[],char b[],int lena,int lenb){
int i,j;
for(i=;i<=lena;i++)
for(j=;j<=lenb;j++){
if(a[i-]==b[j-]){
lcs[i][j]=lcs[i-][j-]+;
flag[i][j]=;
}
else{
if(lcs[i][j-]>lcs[i-][j]){
lcs[i][j]=lcs[i][j-];
flag[i][j]=;
}
else{
lcs[i][j]=lcs[i-][j];
flag[i][j]=;
}
}
}
}
void printlcs(char a[],char b[],int lena,int lenb){
int i=lena;
int j=lenb;
int len=;
int rec[];
while(i>&&j>){
if(flag[i][j]==){
rec[len++]=a[i-];
i--,j--;
}
else if(flag[i][j]==) j--;
else if(flag[i][j]==) i--;
}
len--;
while(len>=){
printf("%c",rec[len--]);
}
printf("\n");
}
int main(){
while(~scanf("%s%s",a,b)){
int lena=strlen(a);
int lenb=strlen(b);
findlcs(a,b,lena,lenb);
printlcs(a,b,lena,lenb);
memset(flag,,sizeof(flag));
memset(lcs,,sizeof(lcs));
}
return ;
}