[5582] 공통 부분 문자열 in python

 > dp 문제

 

두 문자열의 공통 부분을 찾는 문제였다.

이 문제는 다이나믹 프로그래밍을 이용하여 구할 수 있다.

 

a 문자열이 ADABRA

b 문자열이 ECADADABR 이라고 하면

가장 긴 공통 부분 문자열은 ADABR이다.

즉 길이는 5가 된다.

 

이를 구하려면 아래와 같이 총 6개의 리스트를 필요로 함!

저번에 풀었던 기타리스트 1495번 문제와 비슷하다.

https://eboong.tistory.com/449

[1495] 기타리스트 in python

	E	C	A	D	A	D	A	B	R
A	0	0	1	0	1	0	1	0	0
D	0	0	0	2	0	2	0	0	0
A	0	0	1	0	3	0	3	0	0
B	0	0	0	0	0	0	0	4	0
R	0	0	0	0	0	0	0	0	5
A	0	0	1	0	1	0	1	0	0

 

여기서는

dp[i][j]=dp[i-1][j-1]+1이 된다.

 

다이나믹 프로그래밍을 할 때 어떤 걸 더해줘야하는지가

가장 헷갈린다. ㅠㅠ

 

여기서는

해당 문자열 바로 전에 이어지고 있던 부분 문자열이 있는지 확인을 하고

만약 부분 문자열이 이어지고 있다면 그 길이에 1을 더해주는 방식으로 구한다.

 

아래 코드는

pypy3로 돌려야 시간초과가 일어나지 않는다.

 

a, b = input(), input()
lenA = len(a)
lenB = len(b)
dp = [[0 for _ in range(lenB + 1)] for _ in range(lenA + 1)]
answer = 0

for i in range(1, lenA + 1):
    for j in range(1, lenB + 1):
        if a[i - 1] == b[j - 1]:
            dp[i][j] += dp[i - 1][j - 1] + 1
            answer = max(answer, dp[i][j])
print(answer)