[백준] 5582-공통 부분 문자열(C++)

문제링크:https://www.acmicpc.net/problem/5582

5582번: 공통 부분 문자열

 

공통 부분 문자열을 찾는 문제입니다. n의 범위가 4000까지입니다.

 

일반적인 구현방법을 생각해볼때 O(n^3)이 됩니다. 이때 최악의 경우 64,000,000,000 번 반복되기에 당연히 시간초과입니다.

 

n^2 번의 계산법을 찾아야합니다. 

 

저는 표를 만들어 보며 규칙을 찾았습니다. 

	A	A	B	C	A	W
A	1	1	0	0	1	0
B	0	0	1	0	0	0
C	0	0	0	1	0	0
A	1	1	0	0	1	0

 

보이시나요? 이전 배열값에서 1을 더한 값이 자신의 최대연속배열값입니다.

 

점화식은 dp[i][j] = dp[i - 1][j - 1] + 1 입니다. 

 

	A	A	B	C	A	W
A	1	1	0	0	1	0
B	0	0	2	0	0	0
C	0	0	0	3	0	0
A	1	1	0	0	4	0

 

 

 

정답코드입니다.

#include <iostream>
#include <string>
using namespace std;
string arr;
string arr2;
int dp[4001][4001] = { 0 };
int result = 0;
int main() {
	cin >> arr;
	cin >> arr2;

	for (int j = 0; j < arr2.size(); j++) {
		if (arr[0] == arr2[j]) {
			dp[0][j] = 1;
			if (result < dp[0][j]) result = dp[0][j];
		}
	}

	for (int j = 0; j < arr2.size(); j++) {
		if (arr[j] == arr2[0]) {
			dp[j][0] = 1;
			if (result < dp[j][0]) result = dp[j][0];
		}	
	}


	for (int i = 1; i < arr.size(); i++) {
		for (int j = 1; j < arr2.size(); j++) {
			if (arr[i] == arr2[j]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
				if (result < dp[i][j]) result = dp[i][j];
			}
		}
	}
	cout << result << endl;

}