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

KMP 연습문제

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

1787번: 문자열의 주기 예측

실패함수를 활용해 구한 값과 정확히 정반대를 요구하는 문제.

접두사와 접미사가 같아지는 최소 길이를 구해서 문자열의 전체 길이와 빼면

문제에서 요구하는 "추정할 수 있는 주기 중 가장 긴 것의 길이" 를 구할 수 있다.

 

실패함수에서 뒤로 돌아가고자 할때

j = fail[j-1];

사용하는 이 구문에서 착안하고

while(dp[i] && fail[dp[i]-1]) dp[i] = fail[dp[i]-1];

계속 뒤로 돌아가게끔 while문을 사용해서 작성해서 답을 구해냈지만

시간초과를 받았다.

 

사실 dp라 써놓고 멍청하게 dp로 안짜서 시간초과를 받은거다

그렇다 dp를 통해서 dp[k] 를 두번 이상 계산하지 않도록 작성해주면

AC를 받을 수 있다.

 

DP를 작성하는데에는 다양한 방법이 있겠지만

점화식 짜기가 나름 어려워보여서 그냥 메모이제이션으로 풀었다.

애초에 윗쪽에 적은 저 코드가 나름 상향식으로 시도해봤던 무언가이다 ㅋㅋㅋ

 

정답이 int범위를 초과할 수 있으니 long long 을 적극적으로 사용하도록 하자

 

소스코드 펼쳐보기

#include <bits/stdc++.h>
#define INF 998244353
using namespace std;
typedef long long ll;

//fail 배열은 조건에 맞는 경우의 최대값을 저장하는중
//근데 원하는건 최소값이에요 
//전체 길이 - 최소값이 주기의 최대값이겠지 ㅇㅇ 

int fail[1234567] = {0};
int dp[1234567] = {0}; // fail의 정반대, 양수 중 가장 최소값 

int memoi(int k){
	if(k==-1 || fail[k] == 0) return INF;
	if(dp[k] != -1) return dp[k];
	return dp[k] = min(fail[k], memoi(fail[k]-1));
}

int main(){
	int N;
	string s;
	cin >> N;
	cin >> s;
	
	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;
	}
	
	//for(int i=0; i<N; i++) printf("{%d} ", fail[i]);
	
	memset(dp, -1, sizeof(dp));
	ll ans = 0;
	for(int i=0; i<N; i++){
		if(memoi(i) != INF){
			ans += (ll)i+1-dp[i];
		}
	}
	cout << ans;
	return 0;
}