[baekjoon] 백준 5582번(파이썬): 공통 부분 문자열

문제

5582번: 공통 부분 문자열

알고리즘

- 반복문을 통해 두 개의 문자열을 확인한다.

- 두 개의 문자열중에 문자가 같다면 dp에 +1로 저장한다.

- 저장된 dp값과 answer 값을 비교하여 더 큰 값을 answer에 저장한다.

코드

import sys
s1 = list(map(str, sys.stdin.readline().strip()))
s2 = list(map(str, sys.stdin.readline().strip()))

dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
answer = 0

# 반복문을 통해 두 개의 문자열을 확인
for i in range(1, len(s1)+1):
    for j in range(1, len(s2)+1):
        # 두 개의 문자열중에 문자가 같다면 dp에 +1로 저장
        if s1[i - 1] == s2[j - 1]:
            dp[i][j] = dp[i-1][j-1] + 1
            answer = max(dp[i][j], answer)

print(answer)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법