백준
[9252] LCS 2
Jcoder
2018. 10. 20. 21:46
#include <iostream>#include <algorithm>#include <string>using namespace std;string s1, s2;int dp[1001][1001] = { 0 };int main(){int i, j;cin >> s1 >> s2;for (i = 1; i <= s1.size(); i++){for (j = 1; j <= s2.size(); j++){if (s1.at(i - 1) == s2.at(j - 1))dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}cout << dp[s1.size()][s2.size()] << endl;i = s1.size();j = s2.size();string s;while (dp[i][j] != 0){if (dp[i][j] == dp[i - 1][j])i--;else if (dp[i][j] == dp[i][j - 1])j--;else{s += s1.at(i - 1);i--, j--;}}reverse(s.begin(), s.end());cout << s;;}