[BOJ] 10942. 팰린드롬?

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

int arr[2001];
int d[2001][2001]; // d is DP

int solve(int st, int end){
    if( st > end ) return 1;
    if( d[st][end] != -1 ) return  d[st][end];
    if( arr[st] != arr[end]) return d[st][end] = 0;
    return d[st][end] = solve(st+1, end-1);
}

int main(){
    memset(d,-1,sizeof(d));
    int n;
    cin >> n;
    for (int i=1; i<=n; i++) {
        scanf("%d",&arr[i]);
    }
    
    int m;
    cin >> m;
    
    int st,end;
    while ( m--) {
        scanf("%d%d",&st,&end);
        printf("%d\n",solve(st, end));
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <memory.h>
using namespace std;

string tmp, str;
int A[1000001 * 2];

void manachers(string S, int N){
    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 && S[i - A[i] - 1] == S[i + A[i] + 1])
            A[i]++;
        
        if (r < i + A[i]){
            r = i + A[i];
            p = i;
        }
    }
}

int main(){
    int n;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++){
        int val;
        scanf("%d", &val);
        
        /*
         tmp += val
         이렇게 하게되면
         val값이 1일 때
         tmp에는 \x01이 들어간다.
         그렇기 때문에 + '0'을 해줘서
         int형인 val값을 string처럼 바꾼다.
         */
        
        // [1] 또는 [2]
        // 둘 다 가능하다.
        tmp += val + '0'; // [1]
//        tmp.push_back(val + '0'); // [2]
    }
    int len = (int)tmp.size();
    str = tmp[0];
    
    for (int i = 1; i < len; i++){
        str += '#';
        str += tmp[i];
    }
    
    manachers(str, (int)str.size());
    
    int q;
    scanf("%d", &q);
    while (q--){
        int s, e;
        scanf("%d %d", &s, &e);
        s--; e--;
        s *= 2; // 중간에 += '#'을 해줬기 때문에 2배씩 증가
        e *= 2; 
        
        int r = A[(s + e) / 2];
        if ((s + e) / 2 + r >= e)
            printf("1\n");
        else
            printf("0\n");
    }
    
    return 0;
}

/*
1. Answer Code
*/
str = tmp[0];
    
    for (int i = 1; i < len; i++){
        str += '#';
        str += tmp[i];
    }
    str += '#';
    manachers(str, (int)str.size());

/*
1. Wrong Code
2. str에 tmp[0]값을 넣지 않고
3. for i의 시작을 0 부터 했다.
*/

//    str = tmp[0];
    for (int i = 0; i < len; i++){
        str += '#';
        str += tmp[i];
    }
    str += '#';
    manachers(str, (int)str.size());

/*
1. Answer Code
2. str에 tmp[0]값을 넣지 않고
3. for문 안에서
4. str += tmp[i];
5. str += '#'; 순서로 넣었다.
*/

int len = (int)tmp.size();
//    str = tmp[0];
    for (int i = 0; i < len; i++){
        str += tmp[i];
        str += '#';
    }
    str += '#';
    manachers(str, (int)str.size());