[5582] 공통 부분 문자열

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

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) 의 시간복잡도를 통해서 해당 문제를 해결할 수 있다.

---

정답코드

	import Foundation
	let A = readLine()!.map{String($0)}
	let B = readLine()!.map{String($0)}
	var dp = Array(repeating: Array(repeating: 0, count: A.count+1), count: B.count+1)
	var ans = 0
	for i in 1...B.count{
	for k in 1...A.count{
	if B[i-1]==A[k-1]{
	dp[i][k] = dp[i-1][k-1]+1
	}
	ans = max(ans,dp[i][k])
	}
	}
	print(ans)

view raw 5582.swift hosted with ❤ by GitHub

---