LCS

#include<iostream>
#include<string>
using namespace std;
 
string a,b;
int lcs[1001][1001];
 
int main(void)
{
	cin >> a;
	cin >> b;
 
	int n=a.size(), m=b.size(); // n,m  <= 1000
 
	// lcs[i][j] : 0 <= i <= n  , 0 <= j <= m
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
		{
 
			if ( a[i-1] == b[j-1] ) // a[i-1] = i-ta litera słowa a
			{
				lcs[i][j] = lcs[i-1][j-1]+1;
			}
			else
			{
				lcs[i][j] = max( lcs[i-1][j] , lcs[i][j-1] );
			}
		}
	}
	cout << lcs[n][m] << endl;
	return 0;
}