#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N][N];
char s1[N],s2[N];
int main()
{
   cin>>s1+1;
   cin>>s2+1;
   int n=strlen(s1+1);
   int m=strlen(s2+1);
   for(int i=1;i<=n;i++)
   {
      for(int j=1;j<=m;j++)
      {
         f[i][j]=max(f[i-1][j],f[i][j-1]);
         if(s1[i]==s2[j])
         {
            f[i][j]=max(f[i][j],f[i-1][j-1]+1);
         }
      }
   }
   cout<<f[n][m];
   return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=101;
int f[N][N];
char s1[N],s2[N];
int main()
{
	int n,m;
	cin>>s1;
	cin>>s2;
	n=strlen(s1);
	m=strlen(s2); 
	for(int i=1;i<n;i++)
	{
		for(int j=1;j<m;j++)
		{
			s1[i][j]=min(f[i-1][j-1],f[i-1][j-1]);
			if(s1[i]!=s2[j])
			{
				s2[i][j]=min(f[i-1][j],f[i-1][j-1]+1); 
			}
		}
	}
	cout<<s2[n][m];
	return 0;
}