백준 11046 : 팰린드롬??

문제 링크

n과 m이 상당히 크므로 어떤 구간에 대해 팰린드롬인지 아닌지를 적어도 O(logn)안에 해결해야 하는데 도저히 모르겠어서 풀이를 찾아보니 처음보는 알고리즘이 있었다.

O(n)만에 각 정점을 중심으로 하는 팰린드롬의 최대 길이를 찾을 수 있는 알고리즘이었다.

Manacher's Algorithm

모든 팰린드롬을 고려해야하므로 dummy문자를 추가하여 진행하였고, 범위가 주어질 때, 그것의 중심으로부터 dp[i]까지의 길이를 고려했을 때, 그 범위가 안에 들어가는지를 판단함으로써 해결하였다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const int INF = 21 * 1e8;
const int MAX = 1e9;
int n;
vector<int> dp;
vector<int> vec;

void palindp(const vector<int>& s)
{
    int r = 0;
    int p = 0;

    int ssize = s.size();
    for(int i = 0;i<ssize;i++)
    {
        if(i <= r) dp[i] = min(dp[2*p-i],r-i);
        else dp[i] = 0;
        while(i - dp[i] -1 >= 0 && i + dp[i] + 1 <ssize &&
        s[i - dp[i] -1] == s[i + dp[i] + 1]) dp[i]++;

        if(i + dp[i] > r)
        {
            r = i + dp[i];
            p = i;
        }
    }
}

bool isbetween(int x,int i)
{
    return (i - dp[i] <= x && x <= i + dp[i]);
}

int main()
{
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    cin>>n;
    vec = vector<int>(2*n);

    for(int i =0;i<n;i++)
    {
        cin>>vec[2*i];
        vec[2*i+1] = -1;
    }

    dp = vector<int>(2*n);

    palindp(vec);
    int m;
    cin>>m;

  

    for(int i = 0;i <m;i++)
    {
        int qs,qe;
        cin>>qs>>qe;

        if(qs > qe) swap(qs,qe);

        qs--; qe--;

        qs*= 2; qe *= 2;
        int qm = (qs + qe)/2;

        if(isbetween(qs,qm) && isbetween(qe,qm))
        {
            cout<<"1\n";
        }
        else
        {
            cout<<"0\n";
        }
        
    }
    
   

    return 0;
}