//David Malec
//UW-Madison ICPC practice week 3
//Solution to problem #10405 on UVa:
//  Longest Common Subsequence

#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

#define MAX_LEN 1000

//since we only want the size of the lcs, not the lcs itself,
//we only really need one row.
//extra location just removes boundary checks from recursion.
int lcs[MAX_LEN + 1]; 
string s1, s2;

int main(int argc, char* argv)
{
    while(getline(cin,s1) && getline(cin,s2))
    {
	memset(lcs, 0, sizeof lcs);
	//note: lcs[0] = 0 throughout rest of loop
	for(int i = 0; i < s1.length(); i++)
	{
	    //diag is the value in the cell up and left of the current one;
	    //we need to save this for the recursion, since only keeping one row
	    //means it gets overwritten before we stop needing it.
	    int diag = 0;
	    for(int j = 0; j < s2.length(); j++)
		if(s1[i] == s2[j]) //go diag. up/left in table
		{
		    diag++;
		    swap(diag, lcs[j+1]);
		}
		else //go left or up in table
		{
		    diag = lcs[j+1];
		    lcs[j+1] = max(lcs[j], lcs[j+1]);
		}
	}
	cout << lcs[s2.length()] << endl;
    }
}
