//@pku 1458 经典的DY问题LCS
//采用备忘录的方法
#include<iostream>
#include<algorithm>
#include<
string>
using namespace std;
#define N 1500
int flag[N][N];
int getlen(
string &s1,
int i,
string &s2,
int j);
int main()
{
string s1,s2;
int max=0;
while(cin>>s1>>s2){
memset(flag,-1,
sizeof(flag));
max=getlen(s1,s1.size()-1,s2,s2.size()-1);
cout<<max<<endl;
}
//end while
return 0;
}
int getlen(
string &s1,
int i,
string &s2,
int j)
{
if(i==-1 || j==-1)
return 0;
else {
if(flag[i][j]!=-1)
return flag[i][j];
if(s1[i]==s2[j])
{
if(i>0 && j>0)
{
flag[i-1][j-1]=getlen(s1,i-1,s2,j-1);
return 1+flag[i-1][j-1];
}
else {
return 1+getlen(s1,i-1,s2,j-1);
}
}
else {
if(i>0 && j>0)
{
flag[i][j-1]=getlen(s1,i,s2,j-1);
flag[i-1][j]=getlen(s1,i-1,s2,j);
return max(flag[i][j-1],flag[i-1][j]);
}
else {
return max(getlen(s1,i,s2,j-1),getlen(s1,i-1,s2,j));
}
}
}
}