🔥

문제

문자열 S, T가 주어졌을 때, 두 문자열의 최장 길이 공통 부분 문자열(LCS)의 길이를 구하자.

입력

S, T는 알파벳 소문자로 구성되어 있다.
두 문자열의 길이는 1이상 3000이하이다.

출력

최장 길이 공통 부분 문자열 (LCS)의 길이를 출력한다.

예제 1 입력

abbbabbbb
aabba

예제 1 출력

4

예제 2 입력

baaababab
ababbbab

예제 2 출력

6

Source

s1 = input()
s2 = input()
LCS = [[0 for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]

for i in range(1, len(s1) + 1):
	for j in range(1, len(s2) + 1):
		if(s1[i - 1] == s2[j - 1]):
			LCS[i][j] = LCS[i - 1][j - 1] + 1
		else:
			LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])

print(LCS[len(s1)][len(s2)])

참고