[BaekJoon] 5582 공통 부분 문자열 (Gold 5) - Python

문제

 

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.

어떤 문자열 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 이하이다.

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

 

입력예시1)

ABRACADABRA
ECADADABRBCRDARA

출력예시1)

5

 

입력예시2)

UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV

출력예시2)

0

---

코드

 

공통 부분 문자열문제다.

이 문제도 이전에 푼 최장 공통 수열 문제처럼 DP로 푼다.

 

점화식도 엄청 비슷하다. 

점화식 보면

for i in range(len(l_1)):
    for j in range(len(l_2)):
        if i == 0 or j == 0: continue
        elif l_1[i] == l_2[j]: LCS[i][j] = LCS[i - 1][j - 1] + 1
        else: LCS[i][j] = 0

이렇다.

 

세 번 째 라인은 마진 정해주는 라인

네 번 째 라인은, 같은 문자일 경우 i, j인덱스의 LCS값을 i - 1, j - 1인덱스값에 1만큼 더해준 값으로 한다

마지막 다섯 번 째 라인은, 다른 문자일 경우 LCS의 값을 그냥 0으로 한다

 

전체코드이다.

 

import sys; input = sys.stdin.readline # 입력 빠르게 하기 위해 sys import 후 input함수 재정의

l_1 = input().rstrip() # 줄바꿈 문자 제거 후 저장
l_2 = input().rstrip() # 줄바꿈 문자 제거 후 저장

LCS = [[0 for _ in range(len(l_2) + 1)] for _ in range(len(l_1) + 1)] # LCS 리스트 만들기
result = 0 # 결과값 저장할 리스트 생성

for i in range(1, len(l_1) + 1):
    for j in range(1, len(l_2) + 1):
        if l_1[i - 1] == l_2[j - 1]: # 점화식 중 같을 경우만 적용. 이유: 맨 처음 LCS리스트를 생성할 때 모든 원소의 값을 0으로 초기화 했기 때문에 다를 경우를 따지지 않아도 된다.
            LCS[i][j] = LCS[i - 1][j - 1] + 1
            result = max(LCS[i][j], result)

print(result) # 결과값 출력

---

실행 화면

 

---

채점 결과

하도 시간초과 나서 혹시나 하고 PyPy3로 올렸더니....

성공 ㅠㅠㅠ