[Codeforces 1138D] Camp Schedule

[Codeforces 1138D] Camp Schedule

Problem - D - Codeforces

문제 설명 : 

0과 1로만 구성된 문자열 s와 t가 주어진다. 목표는 문자열 s에 등장하는 0과 1의 빈도수와 동일하게 문자열을 변형시키는 것인데 그 문자열의 substring으로 문자열t가 최대한 많이 등장하도록 변형시켜야 한다.

 

풀이 : 

조건에서 문자열 t를 최대한 많이 등장하도록 해야 한다. 여기서 substring은 겹치는 것이 가능하다. 예를 들어서 문자열 "aaa"가 있고 패턴이 "aa"라면 총 2개의 substring이 존재하는 것이다. 따라서 나는 우선 문자열 t에서 최장 길이의 공통 prefix와 suffix를 찾아야 한다. 공통부분을 찾으면 현재의 suffix가 다음 등장하는 패턴의 prefix로 공유될 수 있고, 이렇게 해야만 패턴이 최대한 많이 등장시킬 수 있기 때문이다. 예를 들어서 문자열 t가 "0100" 이라면 공통부분은 "0"이다. 이를 계속 이어쓴다면 0100100100...처럼 공통부분을 공유할 수 있게 되는 것이다. 이 공통부분을 찾는 방법은 KMP알고리즘의 실패함수를 이용하면 된다. "0100"을 실패함수로 돌리면 0,0,1,1이 나온다. 이 값의 의미가 곧 prefix와 suffix가 겹치는 최대 길이라는 뜻이므로 내가 문제에서 구하고자 하는 바와 일치한다. 실패함수의 마지막 인덱스 값이 k라면 최대 겹치는 길이가 k라는 뜻이다. 그래서 나는 맨 처음에 문자열 t를 먼저 쓰고, (k+1)부터 문자열 t의 끝까지만 계속 반복하면 된다. 패턴을 다 쓸 수 있는만큼 쓰고 나면, 남은 0과 1을 아무렇게나 나열하면 된다.

 

주의할 점 : 

s에 등장하는 0과 1의 빈도수가 t의 빈도수보다 작은 경우가 있을 수 있다. 이럴 때는 t의 패턴을 단 한번도 완성할 수 없으므로 그냥 s에 등장하는 0과 1의 빈도수 만큼 나열하면 된다.

 

배운 점 : 

KMP알고리즘에 사용되는 실패함수가 어떤 문자열에서 최장 길이의 공통 prefix과 suffix를 찾는데도 사용할 수 있다는 것을 배웠다. 이 외에도 Z알고리즘을 사용해도 된다.

 

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,int> Cord;
typedef long long ll;
/****************************Default Template******************************/
// #define SIZE
// #define IMP
// #define INF
// const int MOD=
struct S{
	int a,b;

	S(){}
	S(int _a,int _b){
		a=_a;
		b=_b;
	}

	const bool operator<(const S &o) const{
		return a<o.a;
	}
};
priority_queue<int> pq;
priority_queue<int,vector<int>,greater<int>> mpq;
map<int,int> mp;
stack<int> st;
set<int> set_i;
/****************************Default Template******************************/
const int SIZE=500009;


char s[SIZE],t[SIZE];
int fail[SIZE];
int main(){
	scanf("%s %s",s,t);
	int s_len=strlen(s),t_len=strlen(t);
	
	int _0=0,_1=0;
	for(int i=0 ; i<s_len ; i++){
		if(s[i]=='0') _0++;
		else _1++;
	}

	int t0=0,t1=0;
	for(int i=0 ; i<t_len ; i++){
		if(t[i]=='0') t0++;
		else t1++;
	}

	fail[1]=0;
	for(int i=1,j=0; i<=t_len ; i++){
		while(j>0 && t[i]!=t[j]) j=fail[j-1];
		if(t[i]==t[j]) fail[i] = ++j;
	}

	if(_0>=t0 && _1>=t1){
		printf("%s",t);
		_0-=t0,_1-=t1;
		int st=fail[t_len-1];
		while(_0>0 && _1>0){
			for(int i=st ; i<t_len ; i++){
				if(t[i]=='0' && _0>0){
					printf("0");
					_0--;
				}
				else if(_1>0){
					printf("1");
					_1--;
				}
			}
		}
	}

	while(_0>0){
		printf("0");
		_0--;
	}
	while(_1>0){
		printf("1");
		_1--;
	}

	return 0;
}