[백준-5582] 공통 부분 문자열
풀이
예시로 ABRACADABRA , ECADADABR에 대해서 생각해보자
dp를 이중리스트로 선언하고 dp를 돌다가 같은 문자가 만나면 현재의 문자가 각 문자열의 이전문자와 연속되는 문자면 그 연쇡되는 문자의 개수에 +1을 해준다.
dp[i][j]=dp[i-1][j-1]+1
문자가 다르면 연속되지 않으므로 0으로 둔다.
코드
import sys
input = sys.stdin.readline
s1=input().strip()
s2=input().strip()
dp=[[0]*(len(s2)+1) for _ in range(len(s1)+1)]
mx=0
for i in range(1,len(s1)+1):
for j in range(1,len(s2)+1):
if s1[i-1]==s2[j-1]:
dp[i][j]=dp[i-1][j-1]+1
mx=max(mx,dp[i][j])
print(mx)
수행시간: 460ms(pypy3, python3로 돌리면 시간초과난다)
Author And Source
이 문제에 관하여([백준-5582] 공통 부분 문자열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sue06004/백준-5582-공통-부분-문자열저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)