문제

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

예를 들어, "최백준"과 "백준온라인"의 LCS는 "백준"이고, "스타트링크"와 "스트라토캐스터"의 LCS는 "스트"이다.

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

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

len_a, len_b = len(string_A), len(string_B)

LCS = [[0] * (len_b + 1) for _ in range(len_a + 1)]

for i in range(len_a + 1):
    for j in range(len_b + 1):
        if i == 0 or j == 0:
            LCS[i][j] = 0
        elif string_A[i-1] == string_B[j-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
for i in range(1, len_a+1):
    for j in range(1, len_b+1):
        len_lcs = max(len_lcs, LCS[i][j])
        
print(len_lcs)

백준 15482 한글 LCS