1

1

2

3

4

5

6

7

8

9

#include <iostream>
#include <cstring>
using namespace std;

int dp[1005][1005];
int main() {
	memset(dp, 0, sizeof(dp));
	string a, b;
	cin >> a >> b;
	int na = a.size(), nb = b.size();
	for (int i = 1; i <= na; i++) {
		for (int j = 1; j <= nb; j++) {
			if (a[i - 1] == b[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[na][nb];
	return 0;
}