백준 2401번 최대 문자열 붙여넣기

문제

어떤 긴 문자열이 주어지고 여러 개의 짧은 문자열들이 주어질때 이때 짧은 문자열을 긴 문자열에 붙여 넣을때 가장 길게 붙여 넣는 경우를 찾아라. 단 이때 짧은 문자열들끼리는 교차 할 수 없다. (‘aabbc'  에  'aab' 와 'bbc' 둘 다 붙여 넣는 것은 불가능하다.) 또, 짧은 문자열은 여러 번 사용할 수 있다.

문제풀이

사용한 알고리즘 : KMP, DP
algoshipda 님의 코드를 참고하여 작성하였습니다.

(0) 주의 ( 제가 굉장히 많이 실패한 방법 )

 미리 짧은 문자열에 대해 긴 문자열의 어디부터 붙여 넣을 수 있는지 찾아 저장해 놓고 DP 를 돌릴 경우 메모리가 초과 되더라고요....
 메모리 제한이 128MB ( int 32*10^6 개 ) 인데, 최악의 경우 저장해야 하는 integer 가
 (긴 문자열 각 지점(길이)) * (지점 별로 짧은 문자열이 다 들어가면) = 10^5 * 500 > 32*10^6 가 됩니다...
 저는 아직 이 방법으로 푸는 법을 해결하지 못하였습니다.

(1) 코드 9~10

 ' dp[x] : 긴 문자열의 x 글자까지 넣을 수 있는 짧은 문자열의 총 길이의 최대 ' 로 설정하였습니다. 구하고자 하는 건 dp[L-1] 이겠죠. ( L : 긴 문자열 길이 )

(2) 코드 11~16

 보통 KMP 돌릴 때, 긴 문자열을 0~L-1 탐색하면서, 하나의 짧은 문자열이 몇 개나 들어갈 수 있는지 봅니다.
 이 문제에서는 0~L-1 탐색하면서 500개의 짧은 문자열을 한번에 탐색 할 것입니다.
 따라서 각 짧은 문자열의 탐색이 어디까지 되었는지 저장할 행렬이 하나 필요합니다.
 이를 memory 라고 이름 붙여주었습니다.

(3) 코드 26~31

 각 짧은 문자열의 fail 함수를 만들어줍니다.

(4) 코드 34~50

 긴 문자열을 0~ L-1 순서로 탐색하며 dp[0] 부터 dp[L-1] 까지 차례로 만들어줍니다.

 1. 0~i 까지에는 0~i-1 까지에 넣을 수 있는 짧은 문자열을 그대로 넣을 수 있습니다.
 2. N 개의 짧은 문자열을 한번에 탐색할 것입니다. 따라서 과정 (3) 에서 만들어 놓은 memory 라는 행렬을 이용하여 전에 어디까지 탐색하였는지 저장하며 진행합니다.
 3. 만약 어떤 짧은 문자열을 넣을 수 있다면 dp 값을 최신화 해줍니다.

	// algoshipda 님의 코드를 참고하여 작성햐였습니다.
	#include <bits/stdc++.h>
	using namespace std;
	int N, L;
	string Long;
	string Short[505];
	int fail[505][10005]; // 500개의 짧은 문자열의 fail
	// dp[x] : 긴 문자열 x까지 넣을 수 있는 짧은 문자열 길이의 총합의 최대.
	int dp[100005];
	// KMP 를 사용할 때 fail을 따라가는 index ( 보통 j 라고 놓음 ) 로 돌아야 하는데,
	// 긴 문자열을 0번째 글자부터 차례로 보면서 갈 때,
	// 한번에 하나의 짧은 문자열을 하나만 보는 것이 아닌,
	// N 개의 짧은 문자열을 다 보며 지나가기때문에
	// 각각의 짧은 문자열을 어디까지 봤었나를 memory 행렬을 만들어 기억한다.
	int memory[505];
	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> Long;
	L = Long.length();
	cin >> N;
	for (int i = 0; i < N; ++i) {
	cin >> Short[i];
	// 각 짧은 문자별 fail 함수 만들기
	int M = Short[i].length();
	for (int idx = 1, j = 0; idx < M; ++idx) {
	while (j > 0 && Short[i][idx] != Short[i][j]) j = fail[i][j - 1];
	if (Short[i][idx] == Short[i][j]) fail[i][idx] = ++j;
	}
	}
	for (int i = 0; i < L; ++i) {
	if(i>0) dp[i] = dp[i-1]; // 전에까지 만든건 무조건 만들 수 있습니다.
	for (int j = 0; j < N; ++j) { // N 개의 단어.
	int M = Short[j].size();
	while (memory[j] > 0 && Long[i] != Short[j][memory[j]]) memory[j] = fail[j][memory[j] - 1];
	if (Long[i] == Short[j][memory[j]]) {
	if (memory[j] == M-1) { // 짧은 단어를 끝까지 다 넣은경우
	// i에 j 단어를 넣은다면 dp[i-M] + j단어 길이임
	int temp = i - M >= 0 ? dp[i - M] : 0;
	temp += M; // 이번에 들어가는 단어
	dp[i] = max(dp[i], temp); // dp 값 최신화
	memory[j] = fail[j][memory[j]];
	}
	else memory[j]++;
	}
	}
	}
	cout << dp[L-1] << '\n';
	return 0;
	}

view raw BOJ 2401.cpp hosted with ❤ by GitHub