经典动态规划例子，算法导论上有介绍。
设X=（X1,X2,...Xm）, Y=(Y1,Y2,...,Yn), dp[i][j]代表X1...Xi 和Y1...Yj 的最长公共子序列，我们要求到是dp[m][n].
if Xi==Yj dp[i][j]=dp[i-1][j-1]+1
else dp[i][j]=Max(dp[i-1][j],dp[i][j-1]).
#include <iostream>
#include <string>
using namespace std;
#define MAX 500
string X,Y;
int dp[MAX][MAX];
int solve()
{
int xSize,ySize;
xSize = X.size();
ySize = Y.size();
if( xSize == 0 || ySize == 0 ) return 0;
int i,j;
//自底向上
for(i=1;i<=xSize;i++)
for(j=1;j<=ySize;j++)
{
if(X[i-1] == Y[j-1])
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
}
return dp[xSize][ySize];
}
int main()
{
while(cin>>X>>Y)
{
cout<<solve()<<endl;
}
return 0;
}