#include<bits/stdc++.h>
using namespace std;
#define FR0(i,N) for(i=0;i<(N);i++)
#define FR1(i,N) for(i=1;i<=(N);i++)
#define FRN(i,k,N) for(i=k;i<(N);i++)
#define pf printf
#define db double
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define sci(n) scanf("%d",&n)
#define scl(n) scanf("%lld",&n)
#define scf(n) scanf("%f",&n)
#define scd(n) scanf("%lf",&n)
#define scs(s) scanf("%s",&s)
#define scll(n) scanf("%%I64d",&n)
#define PI acos(-1.0)
#define LL long long
#define MX 1000005
#define MOD 1000000007
typedef long long int ll;
bool status[1100002];
int dp[5010][5010];
int main()
{
   string s1,s2;
   while(getline(cin,s1))
   {
       getline(cin,s2);
       int len1=s1.length();
       int len2=s2.length();
       memset(dp,0,sizeof(dp));
       for(int i=1;i<=len1;i++)
       {
           for(int j=1;j<=len2;j++)
           {
               if(s1[i-1]==s2[j-1])
               {
                   dp[i][j]=dp[i-1][j-1]+1;
               }
               else
               {
                   dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
               }
           }
       }
      // cout<<dp[len1][len2]<<endl;
      printf("%d\n",dp[len1][len2]);
   }
}
 
 

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBGUjAoaSxOKSBmb3IoaT0wO2k8KE4pO2krKykKI2RlZmluZSBGUjEoaSxOKSBmb3IoaT0xO2k8PShOKTtpKyspCiNkZWZpbmUgRlJOKGksayxOKSBmb3IoaT1rO2k8KE4pO2krKykKI2RlZmluZSBwZiBwcmludGYKI2RlZmluZSBkYiBkb3VibGUKI2RlZmluZSBtYXgzKGEsYixjKSBtYXgobWF4KGEsYiksYykKI2RlZmluZSBtaW4zKGEsYixjKSBtaW4obWluKGEsYiksYykKI2RlZmluZSBzY2kobikgc2NhbmYoIiVkIiwmbikKI2RlZmluZSBzY2wobikgc2NhbmYoIiVsbGQiLCZuKQojZGVmaW5lIHNjZihuKSBzY2FuZigiJWYiLCZuKQojZGVmaW5lIHNjZChuKSBzY2FuZigiJWxmIiwmbikKI2RlZmluZSBzY3Mocykgc2NhbmYoIiVzIiwmcykKI2RlZmluZSBzY2xsKG4pIHNjYW5mKCIlJUk2NGQiLCZuKQojZGVmaW5lIFBJIGFjb3MoLTEuMCkKI2RlZmluZSBMTCBsb25nIGxvbmcKI2RlZmluZSBNWCAxMDAwMDA1CiNkZWZpbmUgTU9EIDEwMDAwMDAwMDcKdHlwZWRlZiBsb25nIGxvbmcgaW50IGxsOwpib29sIHN0YXR1c1sxMTAwMDAyXTsKaW50IGRwWzUwMTBdWzUwMTBdOwppbnQgbWFpbigpCnsKICAgc3RyaW5nIHMxLHMyOwogICB3aGlsZShnZXRsaW5lKGNpbixzMSkpCiAgIHsKICAgICAgIGdldGxpbmUoY2luLHMyKTsKICAgICAgIGludCBsZW4xPXMxLmxlbmd0aCgpOwogICAgICAgaW50IGxlbjI9czIubGVuZ3RoKCk7CiAgICAgICBtZW1zZXQoZHAsMCxzaXplb2YoZHApKTsKICAgICAgIGZvcihpbnQgaT0xO2k8PWxlbjE7aSsrKQogICAgICAgewogICAgICAgICAgIGZvcihpbnQgaj0xO2o8PWxlbjI7aisrKQogICAgICAgICAgIHsKICAgICAgICAgICAgICAgaWYoczFbaS0xXT09czJbai0xXSkKICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgZHBbaV1bal09ZHBbaS0xXVtqLTFdKzE7CiAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICBkcFtpXVtqXT1tYXgoZHBbaS0xXVtqXSxkcFtpXVtqLTFdKTsKICAgICAgICAgICAgICAgfQogICAgICAgICAgIH0KICAgICAgIH0KICAgICAgLy8gY291dDw8ZHBbbGVuMV1bbGVuMl08PGVuZGw7CiAgICAgIHByaW50ZigiJWRcbiIsZHBbbGVuMV1bbGVuMl0pOwogICB9Cn0KCg==

YmNhY2JjYWJiYWNjYmFiCmJjY2FiY2NiYmFiYWNiYwphMWIyYzNkNGUKenoxeXkyeHgzd3c0dnYKYWJjZGdoCmFlZGZocgphYmNkZWZnaGlqa2xtbm9wcXJzdHV2d3h5egphMGIwYzBkMGUwZjBnMGgwaTBqMGswbDBtMG4wbzBwMHEwcjBzMHQwdTB2MHcweDB5MHowCmFiY2RlZmdoaWprbG1uenl4d3Z1dHNycXBvCm9wcXJzdHV2d3h5emFiY2RlZmdoaWprbG1u

bcacbcabbaccbab
bccabccbbabacbc
a1b2c3d4e
zz1yy2xx3ww4vv
abcdgh
aedfhr
abcdefghijklmnopqrstuvwxyz
a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0q0r0s0t0u0v0w0x0y0z0
abcdefghijklmnzyxwvutsrqpo
opqrstuvwxyzabcdefghijklmn