백준 16570 앞뒤가 맞는 수열 c++ (kmp)

문제 출처 : https://www.acmicpc.net/problem/16570

16570번: 앞뒤가 맞는 수열

문제

수열 (a1, a2, ⋯, aN) 이 다음의 성질을 가지면 그 수열은 k-앞뒤수열 이라고 한다.

(a1, a2, ⋯, ak) = (aN-k+1, aN-k+2, ⋯ , aN), 1 ≤ k < N

어떤 수열이 k-앞뒤수열일 때, k의 최댓값 k*를 그 수열의 앞뒤계수라고 한다.

우리는 수열의 앞뒤가 맞게 만들기 위해 수열의 연속된 앞부분을 자를 수 있다.

예를 들어 (a1, a2, ⋯, aN) 에서 (a1, a2) 을 제거하면 (a3, a4, ⋯ , aN) 가 된다.

주어진 수열  (A1,A2, ⋯ , AN)의 앞부분을 얼마나 잘라야 앞뒤계수를 최대로 만들 수 있을까? 단, 그러한 방법은 2가지 이상일 수 있다. 그리고 자르는 방법에는 "아무것도 자르지 않는 것" 도 포함한다.

입력

첫 번째 줄에 N이 주어진다. (2 ≤ N ≤ 1,000,000)

두번째 줄에 N개의 정수 A1,A2, ⋯ , AN이 공백으로 구분되어 주어진다. (-231 ≤ Ai ≤ 231-1)

출력

앞부분을 잘라서 앞뒤수열로 만들 수 있다면, 그렇게 자른 후 수열의 앞뒤계수 최댓값과 그렇게 자르는 방법의 수를 공백으로 구분하여 출력한다. 어떻게 잘라도 앞뒤계수가 존재하지 않으면 -1 을 출력한다.

알고리즘 분류

• 문자열
• kmp

풀이

kmp의 실패 함수를 이용하는 문제이다.

처음엔 앞의 인덱스부터 한 개씩 줄여가면서 모든 경우에 대해 실패 함수를 만들었는데,

입력 값이 백만인데 정말 무지성이었다.

실패 함수 만드는 데만 O(N)인데 무슨 생각으로 N개 만큼 실패 함수를 만들었을까.

이후엔, 가장 처음으로 나오는 실패 함수 table[table.size()-1]>0인 경우가 최대 k라고 생각하여 (주어진 예제는 통과한다.) k를 찾은 이후로는 앞에서부터 인덱스를 하나씩 줄여가며 pattern[start]~pattern[start+k]와

pattern[n-k]~pattern[n-1]을 비교하여 같은 경우 cnt++ 해주었으나, 38퍼에서 틀렸다고 뜨는 걸 보니,

위의 방식으로 구한 k가 최대가 아닌 경우가 있는 것 같다.

결국 문제에 대한 풀이를 찾아봤고, kmp 풀이는 아니지만 해당 풀이를 통해 뒷 수열은 항상 n-1로 끝나니,
수열의 뒷부분부터 최대 k, 최대 k일 때의 앞뒤 수열을 구해야 한다는 힌트를 얻었다.

 

위의 힌트로 떠오른 kmp 풀이는, 주어진 pattern을 거꾸로 뒤집어 실패 함수를 구하는 것이다.

11

2 5 2 5 2 5 2 8 2 5 2

위의 입력이 주어졌을 때 거꾸로 뒤집으면

2 5 2 8 2 5 2 5 2 5 2 이고, 이것의 실패 함수는

0 0 1 0 1 2 3 2 3 2 3 이다.

실패 함수의 요소는 곧 접두사/접미사의 길이 즉 k를 뜻하며 이중 가장 큰 값이 나오는 개수가 정답이 된다.

입력을 거꾸로 뒤집음으로써, 고정인 뒷부분 수열을 접두사, 해당 접두사를 접미사로 가지는 실패 함수가 완성된다.

위의 결과에서 최대 k는 3이고, 3이 3번 나온 것은, 3의 길이를 가진 접두사 (2 5 2)를 접미사로 가지는 앞뒤 수열이 3개 존재하다는 것이다.

코드

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> makeTable(vector<int> &pattern) {
	vector<int> table(n, 0);
	int j = 0;
	for (int i = 1; i < n; i++) {
		while (j > 0 && pattern[i] != pattern[j]) {
			j = table[j - 1];
		}
		if (pattern[j] == pattern[i]) {
			table[i] = ++j;
		}
	}
	return table;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	//2<=n<=1000000
	cin >> n;
	vector<int> pattern(n);
	for (int i = 0; i < n; i++) {
		cin >>pattern[n-1-i];
	}
	vector<int> table = makeTable(pattern);
	int maxK = 0;
	int cnt = 0;
	for (int i = 1; i < table.size(); i++) {
		if (maxK < table[i]) {
			maxK = table[i];
			cnt = 1;
		}
		else if (maxK == table[i]) {
			cnt++;
		}
	}
	if (maxK == 0) {
		cout << -1;
	}
	else {
		cout << maxK << ' ' << cnt;
	}


	return 0;
}