BOJ 10942번 팰린드롬?

BOJ : https://www.acmicpc.net/problem/10942

github : https://github.com/junho0956/Algorithm/blob/master/10942/10942/%EC%86%8C%EC%8A%A4.cpp

 

manacher 알고리즘을 공부하고, 문제를 해결하였다.

사실 2차원의 dp로도 해결할 수 있는데 좀더 빠르며, 팰린드롬 관련해서 많이 쓰이는 알고리즘 이기에

연습도 할 겸 사용하였다.

 

단, manacher 알고리즘은 홀수 기준의 문자열만 판단가능하기 때문에

이 문제에서 짝수가 나올 수 있다는 것을 감안하여

숫자 중간중간에 임의의 값을 삽입하여 홀수로 만들고 문제를 해결하였다.

 

// manacher's algorithm
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
int dp[4010];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    string str;
    int N; cin >> N;
    int len = N * 2 - 1;
    for (int i = 0; i < N; i++) {
        int num; cin >> num;
        str += num + '0';
        str += '#';
    }
 
    int r, p;
    r = p = 0;
    for (int i = 0; i < len; i++) {
        if (i <= r) dp[i] = min(r - i, dp[p * 2 - i]);
        else dp[i] = 0;
 
        while (i + dp[i] + 1 < len && i - dp[i] - 1 >= 0 && str[i + dp[i] + 1] == str[i - dp[i] - 1]) dp[i]++;
        if (i+dp[i] > r) {
            r = i + dp[i];
            p = i;
        }
    }
 
    int T; cin >> T;
    while (T--) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        a *= 2;
        b *= 2;
        int mid = (a + b) / 2;
        if (mid + dp[mid] >= b) cout << "1\n";
        else cout << "0\n";
    }
 
    return 0;
}