문제
https://www.acmicpc.net/problem/17218
문제해설
문자열 2개가 주어지고 두 문자열에서 가장 긴 부분 문자열을 구하면 된다.
문제풀이
그냥 LCA 알고리즘을 써서 해결할 수 있다.
다만 기본 LCA에서는 문자열의 길이만 구하기 때문에
직접 문자열을 찾는 추가적인 구현만 하면 된다.
문자열을 구하는 방법은 LCA의 원리를 이용하면 된다.
LCA배열 가장 끝에서 시작하여
예를들어 n,m이 끝이라고 하면
(n, m)으로 재귀를 시작하여
만약 두 문자열이 같다면 문자열을 출력하고 (n-1, m-1)을 호출
문자열이 서로 다르다면 위 또는 왼쪽에서 같은 수를 가진 부분을 찾아
위라면 (n, m-1), 왼쪽이라면 (n-1, m)을 호출한다.
이 과정을 n이나 m이 0이 될때까지 재귀를 돌리면 된다.
다만 재귀를 호출하고 문자열을 출력을 해야 원래 문자열 순서로 출력이 된다.
전체코드
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
#include<iostream>
#include<algorithm>
using namespace std;
int arr[42][42];
string str1, str2;
void print(int i, int j) {
if (i == 0 || j == 0)
return;
if (str1[i] == str2[j]) {
print(i - 1, j - 1);
cout << str1[i];
}
else {
if (arr[i][j - 1] == arr[i][j])
print(i, j - 1);
else
print(i - 1, j);
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
string a, b; cin >> a >> b;
str1 = "0" + a;
str2 = "0" + b;
for (int i = 1; i <= a.length(); i++) {
for (int j = 1; j <= b.length(); j++) {
if (str1[i] == str2[j])
arr[i][j] = arr[i - 1][j - 1] + 1;
else
arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
}
}
print(a.length(), b.length());
return 0;
}