[C++] 백준 11046번: 팰린드롬??(Manacher's Algorithm)

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

11046번: 팰린드롬??

 

> 풀이

Manacher's algorithm의 기본 활용 문제이다.

해당 알고리즘은 A라는 array를 완성시키는 것이 목적이며, A[i]에는 i 위치에서의 팰린드롬의 길이가 들어간다.

집합 S가 있고, 그 길이가 N이라고 할 때, 0~N-1 인덱스에 대해서 반복문을 돌아주게 된다.

 

반복문 안에서는 다음과 같은 3개의 steps가 진행된다.

1. A[i]의 초기값을 설정해준다. 이 때 'r'이라는 값이 쓰이는데 이것은 3번째 step에서 i + A[i]값으로 쓰이는데 이것은 즉, 팰린드롬이 끝나는 지점을 말해준다. 다시 돌아와서, i <= r이라는 condition은 현재 인덱스가 이전에 발견된 어떤 팰린드롬에 속하는지를 암시하게 된다. 이 경우에는 min(r-i, A[2*p - i])로 A[i]를 초기화시킨다. 먼저, 2*p - i라는 인덱스는, 현재 속해있는 팰린드롬의 대칭점이다.(p는 팰린드롬 중점의 인덱스를 가리킨다.) 즉, 010에서 두번째 0에 대해 2*p-i를 구하면 0이 된다. 따라서 단순히 생각하면 대칭점에서의 팰린드롬 길이(A[2*p - i]를 넣어주면 될 것만 같다. 하지만 A[i]는 r-i라는 값보다 클 수가 없다. 이를 잘 설명해주는 케이스는 다음과 같다.

위 사진에서 i가 빨간 박스 처리가 된 두번째 '1'를 가리킬 때를 살펴보면, 초기값을 r-i로 상한을 두는 이유에 대해서 바로 알 수 있다.

다음으로 i<=r이 아닐 때, 즉 이전에 발견한 팰린드롬에 속하지 않은 경우에는 0으로 초기화해준다.

이러한 로직을 통해 A[i]에 초기값을 부여해주었는데, 이것은 현재까지 주어진 정보를 통해 A[i]값의 하한(즉, i번째 위치에서는 팰린드롬의 길이가 최소 A[i]이다.)을 정해준 것이다.

 

2. 다음은 while문을 통해 A[i]의 값을 증가시키는 과정이다. condition은 복잡해보이지만, 두 묶음으로 보면 단순하다는 것을 알 수 있으며 다음과 같이 묶이게 된다.

while ((인덱스 값이 유효한가?) && (팰린드롬 검사)) A[i] += 1;

즉, 팰린드롬이 유효한 범위 내에서 A[i]를 계속해서 증가시키는 것이다. step 1을 통해 A[i]의 최소값(초기값)을 정해주었다면, 이번에는 A[i] 값을 확정시키는 것이다.

 

3. 위에서 설명하였던 r, p값을 갱신시켜준다. step 2를 통해 A[i]가 갱신되었는데, 만약 이 팰린드롬이 끝나는 지점이 기존에 있던 r보다 먼 곳에 있다면 새 값을 넣어주는 것이다.

 

이렇게 manacher의 3 steps를 포함한 반복문을 돌려주면 array A가 완성된다. 하지만 알고리즘의 설계상 집합을 그대로 넣으면 올바른 팰린드롬의 길이를 구할 수 없다. 이 문제의 경우에는 값의 범위가 자연수이므로 0이라는 값을 array의 앞뒤와 원소들 사이에 끼워넣어주어야한다. 예를 들어, [1 2 1]이 입력으로 들어왔다면 [0 1 0 2 0 1 0]으로 convert해주어야 한다는 것이다. 이것으로 인해 인덱싱이 조금 달라지므로 이를 유의해야한다.

 

#include <bits/stdc++.h>
using namespace std;

int nums[2000001];
int N;
int A[2000001];

void manacher() {
	int i;

	int r = 0, p = 0;
	for (i = 0; i < N; i++) {
		// Set initial value of A
		if (i <= r) A[i] = min(r - i, A[2*p - i]);
		else A[i] = 0;
		cout << A[i] << " ";

		// Get the palindrome longer
		while ((i - A[i] - 1 >= 0 && i + A[i] + 1 <= N - 1) &&
			(nums[i - A[i] - 1] == nums[i + A[i] + 1])) A[i] += 1;

		// Update r, p
		if (r < i + A[i]) {
			r = i + A[i];
			p = i;
		}
	}
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int i;

	cin >> N;

	// Expand the input: "123" -> " 0102030" for manacher
	for (i = 0; i < N; i++) {
		nums[i * 2] = 0;
		cin >> nums[i * 2 + 1];
	}
	N = N * 2 + 1;
	nums[N - 1] = 0;

	manacher();

	int M;
	cin >> M;
	for (i = 0; i < M; i++) {
		int S, E;
		cin >> S >> E;
		S--; E--;

		// ((S + E)/2) * 2 + 1 = S + E + 1 ... original index to expanded index
		if (A[S + E + 1] >= E - S + 1) cout << "1\n";
		else cout << "0\n";
	}

	return 0;
}