🐹 공통 부분 문자열

1. 문제 링크

5582번: 사다리 타기

2. 코드

Python3 31120KB 2592ms

str1 = input()
str2 = input()
# str1이 더 짧도록 수정
if len(str1) > len(str2):
    str1, str2 = str2, str1
length = len(str1)

dp = [0] * (length)
for idx in range(length):
    # 현재까지 찾은 최대 문자열 길이부터 탐색 
    start = max(dp)
    for l in range(start, length + 1):
        # str1의 범위를 넘어가면 break
        if idx + l > length:
            break
        t = str1[idx:idx+l]
        # 부분 문자열이 다른 문자열에 포함되어 있을 때 
        if t in str2:
            dp[idx] = max(dp[idx], l)
        else:
            break
print(max(dp))

3. 해설

dp[idx]는 문자열 시작점 인덱스(idx)부터의 부분 문자열일 때 가능한 공통 문자열의 최대 길이이다.

두 문자열 중 더 짧은 문자열 각 인덱스를 탐색한다. idx부터 idx+l(부분 문자열 길이)에 포함된 부분 문자열이 다른 문자열에 포함되는지 확인한 후 포함된 경우에는 dp를 l의 값으로 초기화해준다.

idx+l이 짧은 문자열 범위를 벗어나면 다음 위치를 탐색한다. 이때 현재까지의 공통 부분 문자열의 최대 길이부터 탐색한다.(최댓값을 찾는 것이라 굳이 작은 경우를 탐색할 필요가 없다.)