/*
****************************************
Problem: Longest Common Subsequence
****************************************
Ashis Kumar Chanda
ID:   1624
CSE,  DU
****************************************
****************************************
*/
//  dynamic problem = DP

/* 	This code done for char LCS */

#include<stdio.h>
#include<string.h>

#define M 50

int c[M][M], b[M][M]={0};
char x[M], y[M];


void print( int i, int j)
{
	if( i==0 || j==0)
		return ;
	if( b[i][j]==3 )// get same char
	{
		print(i-1, j-1);
		printf("%c",x[i]);
	}
	else if( b[i][j]==2)
		print(i-1, j);
	else
		print(i, j-1);
}


int main()
{
	int i,j, m,n;
	char ch;
    //********* First String input ******
	i=1;
	x[0]='0';
	while( scanf("%c",&ch)!=EOF){
		if( ch==10 )break;
		x[i]=ch;
		i++;
	}
	x[i]=NULL;

	//********* Second String input ******
	i=1;
	y[0]='1';
	while( scanf("%c",&ch)!=EOF){
		if( ch==10 )break;
		y[i]=ch;
		i++;
	}
	y[i]=NULL;

	m= strlen(x);
	n= strlen(y);


	//************** LCS
	for(i=0;i<M ;i++)
		c[i][0]=0;

	for(i=0;i<M ;i++)
		c[0][i]=0;

	for( i=1; i< m; i++){//  must start from 1
		for( j=1; j< n; j++)
		{
			if( x[i]==y[j]){
				c[i][j]= c[i-1][j-1] +1;
				b[i][j]= 3;	// same , sign \\

			}
			else if (c[i-1][j] >= c[i][j-1] )
			{
				c[i][j]=c[i-1][j];
 			    b[i][j] = 2;// sign |
			}
			else{
				c[i][j]=c[i][j-1];
 			    b[i][j] = 1;  // sign <-
			}
		}
	}

	printf("\n output : ");
	// *********  Now print
	print(m-1, n-1);//  call by last cell index,  m is strlen

	printf("\n Lenght is : %d\n", c[m-1][n-1] );
	printf("\n\n	Thanks . . .\n\n");
	getchar();

	return 0;
}