문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

# 9252
import sys
input = lambda: sys.stdin.readline().strip()

string_A = list(input())
string_B = list(input())

LCS = [[0] * (len(string_A)+1) for _ in range(len(string_B)+1)]

for i in range(len(string_B)+1):
    for j in range(len(string_A)+1):
        if i == 0 or j == 0:
            LCS[i][j] = 0
        elif string_A[j-1] == string_B[i-1]:
            LCS[i][j] = LCS[i-1][j-1] + 1
        else:
            LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
            
len_LCS = 0
a, b = 0, 0
for i in range(len(string_B) + 1):
    for j in range(len(string_A) + 1):
        if LCS[i][j] > len_LCS:
            b, a = i, j
            len_LCS = LCS[i][j]
            
print(len_LCS)

if len_LCS == 0:
    exit(0)

string_lcs = []
while a > 0 and b > 0:
    if LCS[b][a] == LCS[b-1][a]:
        b -= 1
    elif LCS[b][a] == LCS[b][a-1]:
        a -= 1
    else:
        string_lcs.append(string_B[b-1])
        a, b = a-1, b-1
        
for s_lcs in string_lcs[::-1]:
    print(s_lcs, end = "")

백준 9252 LCS 2