BOJ 11046번 팰린드롬??

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

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

 

팰린드롬? 과 같은문제인데

범위가 2000에서 백만으로 늘어나면서, 2차원 dp로는 TLE가 발생하는 문제이다.

manacher's algorithm을 통해서 문제를 해결해야한다.

 

단 펠린드롬? 문제처럼 스트링에 숫자+'0' 형식으로 제출했더니

계속 틀린다고 나오길래 아예 숫자형식으로만 사용해봤는데 바로 AC가 떳다.

 

팰린드롬? 문제와 입력되는 값의 범위는 10만이하로 같은데 무슨차이인지 모르겠다,,

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int dp[2000200];
int str[2000200];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    int N; cin >> N;
    int len = N * 2 - 1;
    for (int i = 0; i < len; i++) {
        int num; cin >> str[i++];
    }
 
    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;
}