[cpp 알고리즘] 백준 11046 팰린드롬??

[백준] 11046 팰린드롬?? cpp 풀이

매내처, manacher's, 문자열

문제출처:

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

11046번: 팰린드롬??

 

문제 요약

- 자연수 N개(1<=N<=1,000,000)가 주어지고, 총 M번(1<=M<=1,000,000)의 테스트케이스에서 S번쨰 수부터 E번쨰 수가 팰린드롬인지 확인하는 문제이다. 각각의 테스트케이스에 대해 팰린드롬이면 1을, 아니면 0을 출력하면 된다.

- 팰린드롬 : 양쪽이 대칭이 되는 문자열 ex) a, aa, abcba

- 백준 10942 팰린드롬? 과 같은 문제인데, N의 크기가 다르다는 것이 차이. 

 

2023.05.06 - [알고리즘/백준] - [C++ 알고리즘] 백준 10942 팰린드롬?

[C++ 알고리즘] 백준 10942 팰린드롬?

 

풀이 정리

1. 매내처 알고리즘 활용

 

 

C++ 코드

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

int N,M; //수열의 크기, M번 반복
int arr[2000001];
int A[2000001];

void manachers(){
    int r=0, p=0;
    
    for(int i=0; i<N; i++){
        if(i<=r) A[i] = min(A[2*p-i], r-i);
        else A[i] = 0;

        while(i-A[i]-1 >=0 && i+A[i]+1 <= N-1 && arr[i-A[i]-1] == arr[i+A[i]+1])
            A[i]++;
        
        if(r<i+A[i]){
            r=i+A[i];
            p=i;
        }
    }
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> N;
    for(int i=0; i<N; i++) {
        arr[i*2]=0; //짝수 팰린드롬 위해서
        cin >> arr[i*2+1];
    }
    N=N*2+1; //짝수 팰린드롬 위해서 0을 넣었으니, N의값을 글자수*2+1로 해줌
    arr[N-1]=0; //짝수 팰린드롬 위해서
    
    manachers();
    
    cin >> M;
    while(M>0){
        int s,e; cin >> s >> e;
        s--; e--;
        
        if (A[s+e+1] >= e-s+1) cout << 1 << "\n";
        else cout << 0 << "\n";
        M--;
    }
       
    return 0;
}