BOJ-9251

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int dp[1001][1001] = {0};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
	string st1, st2;
    scanf("%s %s", &st1, &st2);
	
    for(int i=1; i<=st2.size(); i++) {
        for (int j=1; j<=st1.size(); j++) {
			if (st2[i-1] == st1[j-1])
				dp[i][j] = dp[i-1][j-1] + 1;
			else
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
		} 
    }
	cout << dp[st2.size()][st1.size()] << endl;
    return 0;
}