Hyun's_Devlog

https://www.acmicpc.net/problem/5582

처음엔 길이가 짧은 문자열에서 부분문자열을 뽑아낸 뒤 길이가 긴 문자열에 포함되는지 여부를 통해서 접근했지만 당연하게도 시간초과.

동적계획법 태그를 보고서 접근법을 생각해 봤지만 결국 풀이를 찾아봤다. 점화식부터 말하면 다음과 같다.

dp[i][k] = dp[i-1][k-1] + 1

여기서 2차원 배열 dp는 해당 위치의 문자로 끝나는 공통 부분 문자열의 길이를 뜻한다.

풀이

문자열 A = "AACD"와 문자열 B = "SSAB"를 기준으로 설명하면 다음과 같이 작동한다.

문자열 A의 길이 N, 문자열 B의 길이 M 일 때, (N+1)*(M+1) 크기의 2차원배열 dp를 생성. 0으로 초기화한다.

1부터 N, 1부터 B까지 2중 반복문을 탐색하면서 점화식을 통해 계산한 값 중 최댓값이 정답이다.

두 문자열의 i번째와 k번째 문자가 일치했다는 것은 두 문자열의 i-1번째와 k-1번째 문자로 끝나는 공통 부분 문자열에 현재 문자를 이어 붙여 한 글자 더 긴 공통부분 문자열을 만들 수 있다는 뜻이 된다.

즉 O(N*M) 의 시간복잡도를 통해서 해당 문제를 해결할 수 있다.

정답코드