백준 BOJ 13506 - 카멜레온 부분 문자열

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

13506번: 카멜레온 부분 문자열

접두사와 접미사가 같으면서 세군데 이상에서 등장하는 부분문자열을 구하는 문제.

메모리초과와 시간초과 둘다 낭낭하게 받아본 문제 되시겠다

생각보다 제한이 빡빡하지 않나 하는 생각이 든다.

 

일단 문자열의 길이를 N이라 했을때

fail[N-1] 을 통해서 접두사와 접미사가 같은 최대 길이 부분문자열을 구할 수 있고,

이 부분문자열을 KMP를 돌려서 3개 이상 탐색되는가? 가 기본적인 사고의 흐름이었다

당연하겠지만서도 이렇게 짜면 WA받는다.

 

S = "aababaa" 와 같은 경우에 fail[6] 은 2이지만, "aa"는 본 문자열에서 3개 이상 탐색되지가 않는다.

 

그럼 부분문자열 길이를 1부터 fail[N-1] 까지 다 체크해보는 경우를 생각하게 되는데,

MLE나 TLE를 받게 될 것이다.

 

바로 앞서 풀었던

https://blog.koderpark.dev/270

백준 BOJ 1787 - 문자열의 주기 예측

의 풀이 처럼,

 

실패 함수 fail[K] 를 구할때 우리는 이미 뒤로 돌아가는 로직을

 j = fail[j-1];

을 통해 구현해 본 바 있다.

부분문자열의 길이 K를 fail[K-1] 로 갱신해가면서 탐색하게 되면,

접두사와 접미사가 같은 모든 부분문자열을 탐색할 수 있고

이 모든 문자열에 대해서 KMP를 돌려서 세번이상 탐색되는지를 확인해주면 AC를 받을 수 있다.

 

중간에 값을 벡터 등에 담아서 처리하려고 시도하면 MLE를 받을 수 있다.

 

소스코드 펼쳐보기

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

int fail[1234567] = {0};
int fail2[1234567] = {0};

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

int kmp(string s1, string s2){
	make_fail(s2);
	
	int N = s1.length();
	int M = s2.length();
	int ans = 0;
	
	for(int i=0,j=0; i<N; i++){
		while(j>0 && s1[i] != s2[j]) j = fail[j-1];
		if(s1[i] == s2[j]){
			if(j == M-1){
				ans++;
				j = fail[j];
			}
			else j++;
		}
	}
	return ans;
}

int main(){
	string s1;
	cin >> s1;
	make_fail(s1);
	
	for(int i=0; i<1234567; i++) fail2[i] = fail[i];
	int K = fail2[s1.length()-1];

	while(K){
		string tmp = s1.substr(0,K);
		if(kmp(s1,tmp) >= 3){
			cout << tmp;
			return 0;
		}
		K = fail2[K-1];
	}
	
	cout << -1;
	return 0;	
}

 

+

 

내가 누구? "Platinum II"