[백준] 5582번 : 공통 부분 문자열

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

5582번: 공통 부분 문자열

ABCD, ACDB 일때 dp 테이블을 다음과 같이 만들 수 있다.

 

ACD와 ABCD의 값을 구할때, AC, ABC의 최대 길이를 +1 해준다.

즉 점화식을 다음과 같이 세울 수 있다.  str[i]==str[j] 일때 , dp[i][j] = dp[i-1][j-1] + 1

str1 = input()
str2 = input()

length1 = len(str1)
length2 = len(str2)

dp = [[0 for _ in range(length2+1)] for _ in range (length1+1)]

maxvalue = 0
for i in range(1, length1+1):
    for j in range(1, length2+1):
        if str1[i-1] == str2[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
            maxvalue = max(maxvalue, dp[i][j])
            
print(maxvalue)