[9252] python : LCS 2

https://www.acmicpc.net/problem/9252

9252번: LCS 2

 

문제

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

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

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

예제 입력 1 

ACAYKP
CAPCAK

예제 출력 1 

4
ACAK

 

문제 풀이

LCS 문제에 backtracking이 추가된 간단한 문제이다. LCS 개념 설명은 아래 글을 참고하길 바란다.

2023.05.21 - [Computer Science/Data structure & Algorithm] - [Algorithm] LCS (Longest Common Sequence)

[Algorithm] LCS (Longest Common Sequence)

 

x = input()
y = input()

lcs = [[[0, 0] for _ in range(len(y) + 1)] for _ in range(len(x)+1)]

CROSS = 0
UP = 1
LEFT = 2

for j in range(1, len(x) + 1):
    for i in range(1, len(y) + 1):
        if x[j-1] == y[i-1]:
            lcs[j][i][0] = lcs[j-1][i-1][0] + 1
            lcs[j][i][1] = CROSS
        elif(lcs[j-1][i][0] < lcs[j][i-1][0]):
            lcs[j][i][0] = lcs[j][i-1][0]
            lcs[j][i][1] = UP
        else:
            lcs[j][i][0] = lcs[j-1][i][0]
            lcs[j][i][1] = LEFT


print(lcs[j][i][0])

#backtracking
result = []

while(1):
    if(lcs[j][i][0] == 0):
        break
    if lcs[j][i][1] == CROSS:
        result.append(x[j-1])
        j -= 1
        i -= 1
    elif lcs[j][i][1] == LEFT:
        j -= 1
    else:
        i -= 1

result.reverse()
for x in result:
    print(x, end='')