[백준 16229] 반복 패턴

문제

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

알고리즘

KMP, Z

풀이

실패 함수의 다양한 특징들을 사용해서 푸는 문제입니다.

이 이상 어떻게 응용되는지는 모르겠으나, 제가 느끼기론 모든 성질을 다 사용한 것 같습니다. 이 문제에서 실패 함수를 $1-BASED$로 구현하게 되면 깔끔해지는 이유를 알 수 있습니다. 실패 함수의 특징에 대한 설명은 아래 사진으로 대체하겠습니다.

(설명을 자세하게 해주신 doju님 감사합니다)

이제 위 사진의 모든 정보를 이용해 접근을 해봅시다. 우리는 1번 특징을 사용해 실패 함수를 계속 반복하게 되면 주어진 문자열 $S$ 에 대해 suffix와 prefix가 동일한 모든 길이$a$를 얻게 됩니다. $a$를 안다면 당연히 2번 특징을 사용해 모든 패턴$p$를 구하게 되고 이를 통해 정답을 갱신해주면 답을 얻을 수 있습니다.

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int fail[100000];
int N, K, ans;
string S;

int main() {
	FAST;
	cin >> N >> K;
	cin >> S;
	for (int i = 1, j = 0;i < N;++i) {
		while (j && S[i] != S[j]) j = fail[j - 1];
		if (S[i] == S[j]) fail[i] = ++j;
	}
	if (N <= K) cout << N;
	else {
		for (int i = fail[N - 1];i;i = fail[i - 1]) {
			//p: 패턴의 길이 , t: 패턴의 등장 횟수
			int p = N - i;
			int t = (N + K) / p;
			if (t >= 2 && t * p >= N) ans = max(ans, p);
		}
		cout << ans;
	}

	return 0;
}