백준5582 공통 부분 문자열

작성일 | In

문제 링크

  • http://icpc.me/5582

문제 출처

  • 2008 JOI 2번

사용 알고리즘

  • DP

시간복잡도

  • O(N2)

풀이

LCS랑 비슷하게 점화식을 세워주면 됩니다.
문자열을 0-based보다는 1-based로 다루는 것이 이 문제를 풀 때는 정신 건강에 이로울 것 같길래 1-based로 바꿔서 풀었습니다.

dp[i][j] = a[i] == b[j] ? dp[i-1][j-1] + 1 : 0
ans = max(dp[i][j])

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

int dp[4040][4040];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	string a, b; cin >> a >> b;
	int n = a.size(), m = b.size();
	a = 'a' + a;
	b = 'b' + b;

	int ans = 0;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1] + 1;
			ans = max(ans, dp[i][j]);
		}
	}

	cout << ans;
}