백준(9252) - LCS 2 Python

백준(9252) - LCS 2

문제풀이: LCS알고리즘, 파이썬

LCS (Longest Common Subsequence) 최장 공통 부 문자열 알고리즘 문제이다.

백준(9252) - LCS 2 문제에서 최장 공통 부 문자열의 예시까지 추가로 출력하는 문제이다.

일단 아래와 같은 2차원 배열을 만드는 방법은 백준(9251) - LCS를 참고하면 된다.

• 위의 그래프에서 최장 부 문자열의 길이는 4인 것을 확인했고, 그 최장 부 문자열이 어떤 것인지 확인 하기 위해서는 뒤에서부터 찾아나가면 된다.

• arr[i-1][j-1], arr[i-1][j], arr[i][j-1] 의 값이 arr[i][j] 값보다 모두 작은 경우를 거꾸로 찾아 나가서 위의 초록색 표기의 ACAK 인것을 확인 할 수 있다.

import sys
input = sys.stdin.readline

S = input().rstrip()
P = input().rstrip()

n = len(S)
m = len(P)
arr = [[0] * (n+1) for _ in range(m + 1)]

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if S[j-1] == P[i-1]:
            arr[i][j] = arr[i-1][j-1] + 1
        else:
            arr[i][j] = max(arr[i][j-1], arr[i-1][j])

answer = []
x = m
y = n
while 1:
    now = arr[x][y]
    if now == 0:
        break
    if arr[x-1][y-1] == (now - 1) and arr[x][y-1] == (now - 1) and arr[x-1][y] == (now-1):
        x -= 1
        y -= 1
        answer.append(S[y])
    else:
        if now == arr[x-1][y]:
            x -= 1
        else:
            y -= 1

print(arr[-1][-1])

if arr[-1][-1] != 0:
    print(''.join(answer[::-1]))