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

KMP P2 자력솔

헉!!!!

 

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

2401번: 최대 문자열 붙여넣기

일단 처음 보고 한 생각은

KMP를 쓰더라도

브루트포싱은 힘들겠구나 였다.

 

문자열을 중복으로 넣을수 있다는 점에서 완탐을 하면

확실하게 시간초과임이 와닿을듯?

 

근데 이 문제는 긴 문자열 S에 어떤 짧은 문자열 s를 매칭 시킬 때,

매칭된 위치가 k라고 하면

S의 [0,k) 까지의 범위는

해당 문자열을 붙여넣던 말던 항상 값이 변하지 않는다.

앞서 문자열을 붙여넣었다면 그 값에 s.length() 만큼이 더해질 것이고,

앞선 문자열이 아무것도 없다면 s.length() 가 매칭된 최고 숫자가 될 것이다.

 

이 앞선 문자열을 붙여넣었는지의 여부 또한 재귀적으로 들어가 볼 수 있다는 점에서,

이 문제가 "겹치는 부분 문제" 를 가진 DP문제라는 감을 잡았다.

 

dp[i] 를 S의 [0,i] 범위 substring 에서 가장 많이 붙여넣은 경우의 짧은 문자열들의 길이의 총합으로 정의했다.

 

S[i] 가 아무런 짧은 문자열과 매칭되지 않는 경우에는 그대로 값을 유지해야 하기 때문에,

dp[i]의 초기값은 dp[i-1] 이 되고,

 

S에서 매칭을 성공한 경우에는

S[i-s.length()] + s.length()

( 문자열을 매칭해서 길이의 총합이 s.length()만큼 늘어난 상황 ) 과

S[i]

( 문자열을 의도적으로 매칭하지 않은 경우 ) 

이 둘중의 최대값으로 가져오면서

문자열의 매칭을 KMP로 처리해주면

시간초과라는 첫 난관을 넘을 수 있다.

 

이제 두번째는 KMP를 돌리면서 발생하는 메모리 초과에 대한 문제인데,

vector<int> 등을 통해 매칭된 부분의 인덱스를 저장하면

S가 극단적으로 길고 s가 극단적으로 짧은 경우에

지나치게 많은 값이 들어가서 메모리 초과를 받게 된다.

 

해결법은 bool 형으로

bool chk[100001][501] = {0};

를 선언해서,

chk[i][j] : i번째 인덱스에서 부분문자열임을 확인한 s의 인덱스가 j.

이렇게 체크해서 관리해줬다.

대략적으로 bool형이 int형에 비해 4배쯤 더 경제적이라고 알고있다.

 

 

 

#include <bits/stdc++.h>
using namespace std;

//dp[i] - str [0,i) 범위에서 가장 많이 붙여넣은 경우의 문자열 길이.
//dp[i] 이고 문자열 str.length() = K 에서
//dp[i] = max(dp[i], dp[i-K] + K)
 
int dp[100001] = {0};
string B[501];
string A;

bool chk[100001][501] = {0};

int fail[10001] = {0};

bool cmp(string &a, string &b){
	if(a.length() != b.length()) return a.length() < b.length();
	return a < b;
}

void make_fail(string B){
	memset(fail, 0, sizeof(fail));
	int M = B.length();
	for(int i=1,j=0; i<M; i++){
		while(j && B[i] != B[j]) j = fail[j-1];
		if(B[i] == B[j]) fail[i] = ++j;
	}
	return;
}

void kmp(int Bidx){
	make_fail(B[Bidx]);
	
	for(int i=0,j=0; i<A.length(); i++){
		while(j && A[i] != B[Bidx][j]) j = fail[j-1];
		if(A[i] == B[Bidx][j]){
			if(j == B[Bidx].length()-1){
				chk[i][Bidx] = true;
				j = fail[j];
			}
			else j++;
		}
	}
	return;
}

int main(){
	int N;
	
	cin >> A >> N;
	for(int i=0; i<N; i++) cin >> B[i];
	for(int i=0; i<N; i++) kmp(i);
	
	for(int i=0; i<A.length(); i++){
		
		if(i) dp[i] = dp[i-1];
		
		for(int j=0; j<N; j++){
			if(chk[i][j]){
				if(i) dp[i] = max(dp[i], dp[i-B[j].length()] + (int)B[j].length());
				else dp[i] = 1;
			}
		}
	}

	cout << dp[A.length()-1];
	return 0;
}

전체적으로 뻑뻑했지만 재밌었던 문제

KMP + 타 알고리즘이 붙어서

티어가 확 오른거같은데

아주달달하다 ^^7