[백준] 16570 앞뒤가 맞는 수열

백준 16570 앞뒤가 맞는 수열

• https://www.acmicpc.net/problem/16570

• 종만북 접두사/접미사 문제와 유사
  https://velog.io/@sunjoo9912/%EC%A2%85%EB%A7%8C%EB%B6%81-20%EC%9E%A5-%EB%AC%B8%EC%9E%90%EC%97%B4

• S의 접두사도 되고 접미사도 되는 문자열의 최대 길이는 S의 부분 일치 테이블 pi[]로 구할 수 있다는 점을 이용

• 수열의 앞부분을 잘라 앞뒤 수열을 만드는 것이 아니라, 입력받은 수열을 거꾸로 저장하여 pi[]를 계산하면 쉽게 답을 얻을 수 있다

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

int n;

//<접두사도 되고 접미사도 되는 문자열의 최대 길이, 나타나는 횟수> 반환
pair<int, int> getPartialMatch(const vector<ll>& N) {
	vector<int> pi(n, 0);

	//최대 길이, 나타나는 횟수
	int maxpi = 0;
	int cnt = 0;

	int begin = 1;
	int matched = 0;
	while (begin + matched < n) {
		if (N[matched] == N[begin + matched]) {
			++matched;
			pi[begin + matched - 1] = matched;
			
			//최대 길이, 나타나는 횟수 갱신
			if (matched > maxpi) {
				maxpi = matched;
				cnt = 1;
			}
			else if (matched == maxpi) {
				++cnt;
			}
		}
		else {
			if (matched == 0) ++begin;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
	return make_pair(maxpi, cnt);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	
    //수열 거꾸로 저장
	vector<ll> num(n, 0);
	for (int i = 0; i < n; ++i) {
		ll input;
		cin >> input;
		num[n - 1 - i] = input;
	}

	pair<ll, ll> res = getPartialMatch(num);

	if (res.first == 0) {
		cout << -1;
		return 0;
	}
	else cout << res.first << " " << res.second;

	return 0;
}