import sys
input = sys.stdin.readline
from collections import deque
seq1 = input().strip()
seq2 = input().strip()
l = len(seq2)
LCS = [0]*l #seq2 길이의 DP 생성
LCSseq = [""]*l
for letter in seq1:
MAX = 0
seq = ""
for i in range(l):
if LCS[i] > MAX:
MAX = LCS[i]
seq = LCSseq[i]
else:
if seq2[i] == letter:
LCS[i] = MAX+1
LCSseq[i] = seq+letter
result = [0,""]
for i in range(l):
if LCS[i]>result[0]:
result = [LCS[i],LCSseq[i]]
print(result[0])
print(result[1])
개인적으로 어려웠던 문제. LCS 1도 어려웠는데 LCS 2도 만만치않았다.
LCS 1의 방식에 추가로 리스트를 하나 더 만들어서 공통된 수열을 저장해놓고 역추적하는것이 중요하다.
오늘의 교훈) LCS에 대해서 더 자세히 공부하자