#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
char s[MAXN],t[MAXN];
int f[MAXN][MAXN];
int ls,lt;
int main()
{
	scanf("%s",s);//读取字符数组s 
	getchar();//过滤换行符 
	scanf("%s",t);//读取字符数组t 
    ls = strlen(s);//s的字符串长度 
    lt = strlen(t);//t的字符串长度 
    /*for(int i=1;i<=ls;i++)
      printf("%c",s[i]);
    printf("\n");*/
    for(int i=ls;i>=1;i--)  s[i]=s[i-1];
    for(int i=lt;i>=1;i--)  t[i]=t[i-1];
    s[0]='*';
    t[0]='@';
	for(int i=1;i<=ls;i++)
	{
		for(int j=1;j<=lt;j++)
		{
			f[i][j]=max(f[i-1][j],f[i][j-1]);
			//如果两个字符相等，才可以作为一个公共字符 
			if (s[i-1]==t[j-1])//注意：字符串的编号是从0开始的 
			{
				f[i][j] = max(f[i][j],f[i-1][j-1]+1);
			}			 
		}
	} 
	printf("%d\n",f[ls][lt]);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
string s,t;
int f[5001][5001];
int main()
{
	cin>>s;
	cin>>t;
	int ls=s.length()-1;//注意，由于字符串从零读入，这里一定要减一
	int lt=t.length()-1;
	for(int i=1;i<=ls;i++)//注意字符串是从零开始输的，但是我们这里的边界就是第0行，已经初始化为0，所以从第1行开始 
	{
		for(int j=1;j<=lt;j++)
		{
			f[i][j]=max(f[i-1][j],f[i][j-1]);//ti不在子序列中或sj不在子序列中
			if(s[i-1]==t[j-1])
			{
				f[i][j]=max(f[i][j],f[i-1][j-1]+1);
			} 
		}
	}
	cout<<f[ls][lt];
	return 0; 
}