#55423: c++ dp 遞迴解
#include <bits/stdc++.h>
using namespace std;
string s1,s2;
int m[1005][1005];
int lcs(int a,int b){
if(a<0||b<0)return 0;
if(m[a][b]!=-1)return m[a][b];
if(s1[a]==s2[b]){
m[a][b]=lcs(a-1,b-1)+1;
}else {
m[a][b]=max(lcs(a-1,b),lcs(a,b-1));
}
return m[a][b];
}
int main(){
while(cin>>s1>>s2){
memset(m,-1,sizeof(m));
cout<<lcs(s1.size()-1,s2.size()-1)<<endl;
}
return 0;
}