[BOJ] 5582 - 공통 부분 문자열 (Python)

 

 

아이디어 #1

 

DP로 가장 긴 공통 부분 문자열의 길이를 찾는다.

 

 

풀이 #1

 

2차원 리스트 dp를 생성하고 두 문자열의 문자를 차례로 비교한다.

두 문자가 같다면 이전 공통 부분 문자열의 길이보다 1 증가시킨 값을 저장하고 결과값을 갱신해 나간다.

Python3로 제출했을 때 시간 초과가 났으며, PyPy3로 제출하여 통과할 수 있었다.

 

S1, S2 = input(), input()
N1, N2 = len(S1)+1, len(S2)+1
dp = [[0]*N2 for _ in range(N1)]
res = 0
for i in range(1, N1):
    for j in range(1, N2):
        if S1[i-1] == S2[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
            res = max(res, dp[i][j])
print(res)

 

 

 

아이디어 #2

 

다른 분의 코드를 참고하니 투 포인터를 사용해 문자열을 슬라이싱하여 부분 문자열을 찾을 수 있었다.

 

 

풀이 #2

 

찾는 부분 문자열의 시작 인덱스 s, 끝 인덱스 e를 0으로 초기화한다.

두 인덱스가 같으면 바로 e만 증가시키고, 그렇지 않으면 해당되는 부분 문자열이 다른 문자열 내에 있는지 확인한다.

공통 부분 문자열이 있는 경우 결과값을 갱신하고, 없으면 s를 증가시킨다.

 

찾은 공통 부분 문자열의 길이보다 작은 길이의 문자열은 찾을 필요가 없어 끝 인덱스를 바로 증가시켜도 된다.

 

S1, S2 = input(), input()
N = len(S1)
s = e = res = 0
while s < N and e <= N:
    if e > s:
        if S1[s:e] in S2:
            res = max(res, e-s)
        else:
            s += 1
    e += 1
print(res)