[Python] 백준 #5582 - 공통 부분 문자열

문제

---

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

5582번: 공통 부분 문자열

 

 

 

풀이

---

a = input()
b = input()

d = [[0 for _ in range(len(b)+1)] for _ in range(len(a)+1)]
m = 0
for i in range(1,len(a)+1):
    for j in range(1,len(b)+1):
        if a[i-1]==b[j-1]:
            d[i][j] = d[i-1][j-1] + 1
            m = max(m,d[i][j])

print(m)

pypy로 제출하였다.

 

이차원 배열을 생성한 후 dp로 풀어준다.

 

이중 for문을 사용하여 푼다.

 

a[i], b[j]가 같으면 d[i][j]에 연속된 문자열의 개수를 적어준다.

이때 d[i-1][j-1]가 앞의 문자열이 반복된 개수이므로 d[i-1][j-1] + 1을 해준다.

 

 

 

출처  - https://dailylifeofdeveloper.tistory.com/114?category=790222