[백준] 5582번: 공통 부분 문자열 (다이나믹 프로그래밍)

 

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

5582번: 공통 부분 문자열

 

이 문제는 DP로 접근해야하는 문제이다.

이중 for문을 돌다가 같은 문자를 만나게 되면 그전까지의 공통 부분 문자열 길이 +1을 dp에 저장한다.

 

파이썬 코드

ans = 0
s1, s2 = input(), input()

dp = [[0] * (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]):
            dp[i][j] = dp[i-1][j-1] + 1
            ans = max(dp[i][j], ans)

print(ans)