[BOJ] 9252 : LCS 2

#include <stdio.h>
#include <algorithm>

int dp[1234][1234];
char s1[1234], s2[1234];

void f(int i, int j) {
	if (!dp[i][j]) return;
	if (s1[i] == s2[j]) {
		f(i-1, j-1);
		putchar(s1[i]);
	}
	else dp[i-1][j] > dp[i][j-1] ? f(i-1, j) : f(i, j-1);
}

int main() {
	scanf("%s\n%s", s1 + 1, s2 + 1);

	int i, j;
	for (i = 1; s1[i]; i++) for (j = 1; s2[j]; j++)
		dp[i][j] = std::max({ dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+(s1[i]==s2[j]) });

	printf("%d\n", dp[--i][--j]);
	f(i, j);

	return 0;
}