[DP] 백준 5582번 “공통 부분 문자열” Python 풀이

문제 링크

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

풀이

• 대표적인 DP 문제이며, 2차원 DP 테이블을 사용해서 풀 수 있습니다.

• 2차원 DP 테이블의 행과 열을 각각의 문자열로 구성한 뒤,

• 이중 for문을 통해 각각의 문자들을 비교하며,

• 각각의 문자가 같다면, 이전 공통 부분 문자열 길이에 1을 더해 저장해나가면 됩니다.

  

코드

# PyPy3로 제출

import sys

# 각각의 문자열
first = sys.stdin.readline().rstrip()
second = sys.stdin.readline().rstrip()

# DP 테이블
dp = [[0] * (len(second)) for _ in range(len(first))]

# 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이
max_value = 0

# DP 진행
for i in range(len(first)):
    for j in range(len(second)):
        # 각각의 문자가 같다면
        if (first[i] == second[j]):
            # 첫 행이거나 첫 열이라면
            if (i == 0 or j == 0):
                dp[i][j] = 1
            # 나머지의 경우
            else:
                dp[i][j] = dp[i-1][j-1] + 1

            # 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이
            max_value = max(max_value, dp[i][j])

print(max_value)

참고

• https://dailylifeofdeveloper.tistory.com/114