[BOJ 11046 // C++] 팰린드롬??

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 11046번 문제인 팰린드롬??이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11046

11046번: 팰린드롬??

이 문제는 전에 쓴 10942번 문제(measurezero.tistory.com/69)와 같은 문제이나, 주어지는 수열의 길이가 2000이 아닌 1000000이라는 차이점이 있다.

따라서, 이전에 사용한 풀이로 이 문제를 풀 수는 없고, 시간복잡도가 더 적은 Manacher's Algorithm을 이용하는 것이 좋다.

 

Manacher's Algorithm은 현재 index가 이미 한번 팰린드롬 문자열 탐색 때 살펴본 범위(boundary) 안에 있다면, 그 범위에 닿았던 중심(center)에 대칭인 index를 중심으로 하는 팰린드롬 문자열 길이만큼 boundary 안쪽에서는 다시 탐색할 필요가 없다는 점을 이용한다. 팰린드롬 문자열의 특징상 그만큼은 이전에 조사한 대로 팰린드롬 문자열임을 알고 있기 때문이다.

 

Manacher's Algorithm은 그냥 사용하면 각 index가 중심인, 홀수 길이의 팰린드롬만을 구할 수 있기 때문에, 문자열에 끼어있을 수 없는 다른 문자 하나를 각 문자 양옆에 하나씩 삽입해 짝수 길이의 팰린드롬 또한 구할 수 있게 변형해줄 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <cmath>
using std::cin;
using std::cout;
using std::min;

int nums[2000002];
int A[2000002];

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

    int len; cin >> len;
    len = 2 * len + 2; // 짝수길이 팰린드롬을 구하기 위한 조작
    int temp;
    for (int i = 1;i < len;i++) {
        if (i & 1) nums[i] = -1;
        else {
            cin >> temp;
            nums[i] = temp;
        }
    }
    int boundary = 0, center = 0; // Manacher's Algorithm
    for (int i = 1;i < len;i++) {
        if (i > boundary) A[i] = 0;
        else A[i] = min(A[2 * center - i], boundary - i);
        while ((i-A[i]-1>0) and ((i+A[i]+1)<len)) {
            if (nums[i - A[i] - 1] == nums[i + A[i] + 1]) A[i]++;
            else break;
        }
        if (i + A[i] > boundary) {
            boundary = i + A[i];
            center = i;
        }
    }
    int N; cin >> N; // 쿼리 처리
    int s, e;
    for (int i = 0;i < N;i++) {
        cin >> s >> e;
        if (A[s + e] > e - s) cout << 1 << '\n';
        else cout << 0 << '\n';
    }
    return 0;
}