#include<fstream>
#include<string>
using namespace std;

void fnReadSubsir(void);
void fnDynamic(void);
void fnWriteSubsir(void);
int fnMax(int nFirst,int nSecond);

int nFirstArray[502],nSecondArray[502];
int nFirstSize,nSecondSize;
int nPinLine[502],nPinColumn[502],nDynamic[502][502];

int main(void) {
	fnReadSubsir();
	fnDynamic();
	fnWriteSubsir();
	return 0;
}

void fnReadSubsir(void) {
	ifstream ifSubsir("subsir.in");
	char chFirstArray[502],chSecondArray[502];
	int nX;
	
	ifSubsir>>chFirstArray>>chSecondArray;
	nFirstSize=strlen(chFirstArray);
	nSecondSize=strlen(chSecondArray);
	ifSubsir.close();
	
	for (nX=1;nX<=nFirstSize;++nX) 
		nFirstArray[nX]=chFirstArray[nX-1]-'a'+1;
	for (nX=1;nX<=nSecondSize;++nX) 
		nSecondArray[nX]=chSecondArray[nX-1]-'a'+1;
}

void fnDynamic(void) {
	int nX,nY;
	for (nX=1;nX<=nFirstSize;++nX) 
		nDynamic[nX][0]=1;
	for (nX=1;nX<=nSecondSize;++nX) 
		nDynamic[0][nX]=1;
	for (nX=1;nX<=nFirstSize;++nX)
		for (nY=1;nY<=nSecondSize;++nY)
			if (nFirstArray[nX]==nSecondArray[nY] && !nPinLine[nX] && !nPinColumn[nY]) {
				nDynamic[nX][nY]=fnMax(nDynamic[nX-1][nY],nDynamic[nX][nY-1]);
				nPinLine[nX]=1;
				nPinColumn[nY]=1;
			} else if (nPinLine[nX] && nPinColumn[nY])
					nDynamic[nX][nY]=nDynamic[nX-1][nY-1]+1;
				else 
					nDynamic[nX][nY]=fnMax(nDynamic[nX-1][nY],nDynamic[nX][nY-1]);
}

void fnWriteSubsir(void) {
	ofstream ofSubsir("subsir.out");
	ofSubsir<<nDynamic[nFirstSize][nSecondSize];
	ofSubsir.close();
}

int fnMax(int nFirst,int nSecond) {
	if (nFirst>nSecond) return nFirst;
	return nSecond;
}