[백준] 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 이하이다.

출력

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

내 풀이

input1 = input()
input2 = input()

def common_string_length(str1, str2):
    subset1 = []
    for i in range(len(str1)):
        for j in range(len(str1)):
            subset1.append(str1[i:j])

    subset2 = []
    for i in range(len(str2)):
        for j in range(len(str2)):
            subset2.append(str2[i:j])
            
    intersection = list(set(subset1)&set(subset2))
    intersection1 = [len(x) for x in intersection]
    intersection1.sort(reverse=True)
    
    return intersection1[0]
 
print(common_string_length(input1, input2))

코멘트

• 메모리 초과로 실패ㅜ
• 푸는 방법이 정해져 있는 문제였다. Dynamic Programming 문제. 여기 참조