반응형
https://www.acmicpc.net/problem/9252
9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
1. LCS 길이 계산
2. LCS 찾기
01234567
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include <iostream>
#include <algorithm>
#include <stack>
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
string a, b;
stack<char> s;
int dp[1002][1002];
void lcs_length() {
rep(i, b.length()) {
rep(j, a.length()) {
if (b[i - 1] == a[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
int len = dp[b.length()][a.length()];
cout << len << '\n';
}
void lcs_find() {
int i = b.length();
int j = a.length();
while (dp[i][j] > 0) {
if (b[i - 1] == a[j - 1]) {
s.push(b[i - 1]);
i--, j--;
}
else {
if (dp[i - 1][j] > dp[i][j - 1]) i--;
else j--;
}
}
while (!s.empty()) {
cout << s.top();
s.pop();
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> b;
lcs_length();
lcs_find();
}
|
cs |
반응형