16570 - 앞뒤가 맞는 수열

step 1

수열을 한번 뒤집어 봅시다. 그럼 앞에 있는 수를 제거하는게 아니라 뒤에 있는 수를 제거하는 문제로 바뀝니다. 그럼 저희는 각 위치마다 앞뒤계수를 구해주면 됩니다.

step 2

앞뒤 계수를 다른말로 하면 접두사와 접미사가 얼마나 일치하는지 입니다. 그리고 이건 KMP에서 실패 함수를 만들때 구합니다. 실패함수를 만들어 준 뒤 가장 큰 숫자가 뭔지, 몇개나 나오는지를 계산해 줍니다.

코드

#include<stdio.h>
int b[2000000],f[2000000];
int main() {
	int i, n,p=0,max=0,maxi=0;
	scanf("%d", &n);
	for (i = n; i >= 1; i--) scanf("%d", &b[i]);
	f[1] = 0;
	for (i = 2; i <= n; i++) {
		while (1) {
			if (b[p + 1] == b[i]) { p++; break; }
			if (p == 0) break;
			p = f[p];
		}
		f[i] = p;
		if (max < p) { max = p; maxi = 1; }
		else if (max == p) maxi++;
	}
	if (max == 0) printf("-1"); else 
	printf("%d %d", max, maxi);
	return 0;
}