백준 9251 LCS

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

 

 이 문제는 두 문자열의 가장 긴 공통서열을 구하는 문제이다. 

 

 이 문제는 전에 ROSALIND에서 풀어본적이 있으므로, https://jangbearbio.tistory.com/41 자세한 사항은 이 링크에 들어가여 참조하길 바란다.

 

import sys
input = sys.stdin.readline

A = ' '+input().rstrip()
B = ' '+input().rstrip()

lcs_map = [['' for _ in range(len(B))] for _ in range(len(A))]

for i in range(len(A)):
    for j in range(len(B)):
        if i==0 or j==0:
            continue
        elif A[i]==B[j]:
            lcs_map[i][j] = lcs_map[i-1][j-1] + A[i]
        else:
            lcs_map[i][j] = max([lcs_map[i-1][j],lcs_map[i][j-1]],key=len)

print(len(lcs_map[len(A)-1][len(B)-1]))