문제
LCS는 두 수열이 주어졌을 때 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 알고리즘이다.
예를 들어 ACAYKP와 CAPCAK의 LCS는 ACSK가 된다.
입력
첫째 줄과 둘째 줄에 문자열이 주어짐
출력
두 문자열의 LCS의 길이를 출력
(1) 마지막 원소가 다른 경우
ACAY와 CAPC의 LCS를 구해보자
이때, ACA-CAP, ACAY-CAP, ACA-CAPC의 LCS는 알고 있다고 가정한다.
여기에서 ACA-CAP의 부분수열 집합은
ACAP-CAP의 부분수열 집합에 완전히 포함되고, ACA-CAPC의 부분수열 집합에도 완전히 포함된다.
그러므로 ACAP-CAPC의 LCS를 구하기 위해서 ACA-CAPC의 LCS와 ACAP-CAP의 LCS 중 더 큰 값을 선택하면 된다.
(2) 마지막 원소가 같은 경우
ACA와 CAPCA의 LCS를 구해 보자
이떄, AC-CAPC의 LCS는 알고 있다고 가정 한다.
ACA-CAPCA의 LCS는 AC-CAPC의 LCS에서 A를 공통 부분 수열의 원소로 추가하면 되는 것이므로 1을 더해 주면 된다.
import sys
a = sys.stdin.readline().rstrip()
b = sys.stdin.readline().rstrip()
table = [[0 for _ in range(len(b))] for _ in range(len(a))]
for i in range(len(a)):
if a[i] == b[0]:
for j in range(i, len(a)): table[j][0] = 1
break
for i in range(len(b)):
if b[i] == a[0]:
for j in range(i, len(b)): table[0][j] = 1
break
for i in range(1, len(a)):
for j in range(1, len(b)):
if a[i] == b[j]: table[i][j] = table[i-1][j-1]+1
else: table[i][j] = max(table[i-1][j], table[i][j-1])
print(table[len(a)-1][len(b)-1])