문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. |
code>>
#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
int memo[1001][1001] = { 0 };
int main()
{
std::ios::ios_base::sync_with_stdio(false);
std::string input1, input2;;
std::cin >> input1 >> input2;
input1 = input1.insert(0, "0");
input2 = input2.insert(0, "0");
for (int i = 1; i < input1.size(); i++)
{
for (auto ii = 1; ii < input2.size(); ii++)
{
if (input1[i] == input2[ii])
memo[i][ii] = memo[i - 1][ii - 1] + 1;
else
memo[i][ii] = std::max(memo[i][ii - 1], memo[i - 1][ii]);
}
}
std::stack<char> stack;
int i = input1.size()-1;
int ii = input2.size()-1;
while (ii > 0 && i > 0)
{
if (input1[i] == input2[ii])
{
stack.push(input2[ii]);
ii--; i--;
}
else
{
if (memo[i - 1][ii] > memo[i][ii-1])
i--;
else
ii--;
}
}
printf("%d\n",stack.size());
while(!stack.empty())
{
printf("%c", stack.top());
stack.pop();
}
printf("\n");
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
1005>ACM Craft (0) | 2018.09.20 |
---|---|
2231>분해합 (0) | 2018.09.02 |
9251>LCS (0) | 2018.08.04 |
1920>수 찾기 (0) | 2018.06.24 |
1780>종이의 개수 (0) | 2018.06.22 |