这是个很老的问题了，最近总是碰到，大三时候学的算法好多都忘记了，不如重新学一遍。
比起XXblog上的教程，我最喜欢的还是这个版本：http://www.ics.uci.edu/~eppstein/161/960229.html
里面的代码干净利落，解释也非常的清晰，一步一步怎么来的都很好。
这个问题是个动态规划的问题，最基本的样子是这样的：
假设当前搜索到字符串A,B中的字符a[i],b[j].
LCS[i,j]表示字串A,B分别在位置[i][j]及以后的最大子序列数量
IF A[i] == B[j]:
LCS[i,j] = 1 + LCS[i+1][j+1] # 当前的算入，然后A，B再往后挪一格
ELSE
LCS[i,j] = max(LCS[i][j+1], LCS[i+1][j]) # 分别挪动A,B后一格看看哪个好
ENDIF
由于这样递归能弄出的子问题里面，好多是重复的，因此我们可以像计算斐波那契数列那样，采用自底向上的方法，用非递归的方式实现。即从字符的末尾往前推导LCS[i][j]，这样当计算LCS[i][j]的时候, LCS[i+1][j]或LCS[i][j+1]已经计算好了。
具体还是看英文教程吧，这里给出C++实现的代码。因为下午例会还得讲PPT，下面的代码用了全局变量传递计算好的序列，有点丑。
#include <iostream>
using namespace std;
/**
* Longest Common Subsequence
*/
int** storeMat;
int max(int x, int y){
return x>y? x:y;
}
int getLCSLength(char* A, char* B){
int sz_A = strlen(A);
int sz_B = strlen(B);
storeMat = new int*[sz_A+1];
for(int i=0; i<=sz_A; i++){
storeMat[i] = new int[sz_B+1]; // Allocate memory
}
for(int i=sz_A; i>=0; i--){
for(int j=sz_B; j>=0; j--){
if(A[i] == '\0' || B[j] == '\0'){
storeMat[i][j] = 0;
} else if (A[i] == B[j]) {
storeMat[i][j] = 1 + storeMat[1+i][1+j];
} else {
storeMat[i][j] = max(storeMat[1+i][j], storeMat[i][1+j]);
}
}
}
return storeMat[0][0];
}
string getLCS(char* A, char* B){
if(NULL == storeMat){
getLCSLength(A, B);
}
int i=0, j=0;
string result;
int sz_A = strlen(A); int sz_B = strlen(B);
while(i < sz_A && j<sz_B){
if(A[i] == B[j]){
result += A[i];
i++;
j++;
} else if (storeMat[i+1][j] > storeMat[i][j+1]){
i++;
} else {
j++;
}
}
return result;
}
int main() {
char a[50], b[50];
scanf("%s %s", a, b);
cout << getLCS(a, b);
return 0;
}