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;
}