http://acm.hdu.edu.cn/showproblem.php?pid=1159
#include<iostream>
#include<string>
using namespace std;
const int M = 1001;
char s[M],t[M];
int dp[M][M];//dp[i][j]表示串s的前i个与串t的前j个的最大匹配
//int track[M][M];//保存路径
/*
void LCS(int i,int j)//输出公共子串
{
    if(i==0 || j==0)
        return ;
    if(track[i][j] == 1)
    {
        LCS(i-1,j-1);
        printf("%c ",s[i-1]);
    }
    else if(track[i][j] == 2)
        LCS(i-1,j);
    else
        LCS(i,j-1);
}
*/
int main()
{
    int i,j,lens,lent;
    while(scanf("%s%s",s,t)!=EOF)
    {
        lens = strlen(s);
        lent = strlen(t);

        for(i=0;i<=lens;i++)
            dp[i][0] = 0;

        for(i=0;i<=lent;i++)
            dp[0][i] = 0;

        for(i=1;i<=lens;i++)
        {
            for(j=1;j<=lent;j++)
            {
                if(s[i-1] == t[j-1])
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    //track[i][j] = 1;
                }
                else if(dp[i][j-1] > dp[i-1][j])
                {
                    dp[i][j] = dp[i][j-1];
                    //track[i][j] = 3;
                }
                else
                {
                    dp[i][j] = dp[i-1][j];
                    //track[i][j] = 2;
                }
            }
        }
        cout<<dp[lens][lent]<<endl;
        //LCS(lens,lent);
        //cout<<endl;
    }
    return 0;
}