[파이썬] 백준 5582 공통 부분 문자열

시간 초과 날 거 알면서도 최대한 줄여보려고 했으나 19%에서 막혔다. 이문제도 dp 를 이용한 것인데 규칙을 이용하면 된다. 시간 초과가 날 거 같은 문제들은 일단 손으로 적으면서 규칙을 찾아야 겠다. 

 

from collections import deque
from itertools import combinations
import sys
 
 
a = input()
b = input()
 
answer = 0
 
if len(list(a))<len(list(b)):
 
    for i in range(0,len(list(a))-1):
        for j in range(i+1,len(list(a))):
            k = a[i:j]
 
            if k in b:
                if (j-i)>answer:
                    answer = (j-i)
            else:
                break
 
else:
    for i in range(0,len(list(b))-1):
        for j in range(i+1,len(list(b))):
            k = b[i:j]
 
            if k in a:
                if (j-i)>answer:
                    answer = (j-i)
            else:
                break
 
 
print(answer)
 

 

 

해답 

 

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)