LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.
LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.
import sys
str1 = sys.stdin.readline().rstrip()
str2 = sys.stdin.readline().rstrip()
arr = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]
for i in range(1, len(str1) + 1):
for j in range(1, len(str2) + 1):
# 만약 첫 문자열 i 번째와 두 번째 문자열 j 번째가 같다면, 현재까지의 최장 공통 부분 수열 +1
if str1[i - 1] == str2[j - 1]:
arr[i][j] = arr[i - 1][j - 1] + 1
# 다르다면, 세로 기준으로 비교한 것과 가로로 비교한 것 중 더 큰 값을 고른다.
else:
arr[i][j] = max(arr[i][j - 1], arr[i - 1][j])
answer = 0
for i in range(1, len(str1) + 1):
for j in range(1, len(str2) + 1):
answer = max(answer, arr[i][j])
print(answer)
if answer > 0:
string_list = []
i = len(str1)
j = len(str2)
while arr[i][j] != 0:
if arr[i][j] == arr[i - 1][j]:
i -= 1
elif arr[i][j] == arr[i][j - 1]:
j -= 1
else:
string_list.append(str1[i - 1])
i -= 1
j -= 1
for a in range(len(string_list)-1, -1, -1):
print(string_list[a], end='')