/*
裸lcs（最大公共子序列）
*/
# include <stdio.h>
# include <algorithm>
# include <iostream>
# include <string.h>
using namespace std;
int c[1010][1010];
int main()
{
    int i,j,lena,lenb;
    char a[1010],b[1010];
    while(~scanf("%s%s",a,b))
    {
        lena=strlen(a);
        lenb=strlen(b);
       memset(c,0,sizeof(c));
        for(i=1;i<=lena;i++)
        {
            for(j=1;j<=lenb;j++)
            {
                if(a[i-1]==b[j-1])
                    c[i][j]=c[i-1][j-1]+1;
                else
                    c[i][j]=max(c[i-1][j],c[i][j-1]);
            }
        }
        printf("%d\n",c[lena][lenb]);
    }
    return 0;
}

hdu 1159 Common Subsequence (lcs)