[Python] 백준 / gold / 5582 : 공통 부분 문자열

문제 링크 : https://www.acmicpc.net/problem/5582

( 문자열 + 다이나믹 프로그래밍 ) 유형 문제. dp table 작성하는 좋은 연습이 된거 같다. 문자열 S = ABCBCD 와 T = BBCDB 가 있을때 최대 공통 부분 문자열은 BCD 다. 연속하는 문자열을 찾는게 핵심이기 때문에 dp table 의 점화식을 다음처럼 작성하면 좋다.

뭔가 적고 나서 보니까 복잡해 보이는데.. 천천히 생각하면서 테이블을 채워보면 하나도 안어렵다.

이 사이트의 예제가 도움이 많이 됐다.
https://lmcoa15.tistory.com/73

기억할 것

• 연속하는 문자열을 비교할 때 dp table 을 작성하면 효율적이다.

파이썬 코드

import sys
S = sys.stdin.readline().strip()
T = sys.stdin.readline().strip()

dp = [[0] * len(T) for _ in range(len(S))]
answer = 0

for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            if i == 0 or j == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i-1][j-1] + 1
            answer = max(answer, dp[i][j])

print(answer)