🐢 공통 부분 문자열

1. 문제 링크

공통 부분 문자열

2. 코드

PyPy3 236364KB 520ms

"""
[5582] 공통 부분 문자열

💛 문제
두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.
어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다.

예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA,
빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR,
빈 문자열 등이 있다.
이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다.
또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.

💚 입력
첫째 줄과 둘째 줄에 문자열이 주어진다.
문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.

💙 출력
첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.
"""

s1 = input()
s2 = input()
result = 0

# 가로 + 1 x 세로 + 1 dp 배열 만들기
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] :
            # 그 전 문자열에서 + 1 해준다
            # 대각선 방향으로 커짐
            dp[i][j] = dp[i-1][j-1] + 1
            result = max(dp[i][j], result)

print(result)

3. 해설

• dp 배열을 만든다
• 부분 문자열이 같다면 해당 dp 배열에 그전 배열값 + 1 을 해준다
• 연속으로 문자열이 같다면 대각선 방향으로 크기가 커질 것이다