카테고리 없음
백준 5582 공통 부분 문자열
작지
2022. 2. 25. 13:11
https://www.acmicpc.net/problem/5582
5582번: 공통 부분 문자열
두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들
www.acmicpc.net
파이썬이 너무 느려!
라는 생각이 절로드는 문제였습니다.
처음엔 문자열 A , B 를 합친 DP = [[0]*(len(A)+1) for i in range(len(B)+1)] 를 사용하여 비교해나갔는데
어째선지 4000*4000에서 시간 초과가 나올줄은 몰랐습니다.
그래서 DP[I] 를 찾아가는 수고를 덜 시키면 낫지 않냐? 라는 생각에
deep.copy를 사용했는데 왠걸 더 느리다는걸 알았고
[:]를 사용하는 편이 빠르다는걸 알았습니다.
import sys
input = sys.stdin.readline
s1 = list(input().rstrip())
s2 = list(input().rstrip())
# s = [[0]*(len(s2)+1) for i in range(len(s1)+1)]
prev = [0]*(len(s2)+1)
answer = 0
for i in range(len(s1)):
cur = [0] * (len(s2)+1)
for j in range(len(s2)):
if s1[i] == s2[j]:
cur[j+1] = prev[j] + 1
answer = max(answer,max(cur))
prev = cur[:]
print(answer)