[BOJ] 13275. 가장 긴 팰린드롬 부분 문자열

#include<iostream>
using namespace std;
const int MAXN = 100001 * 2;
int A[MAXN];

string str;

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(){
    string s;
    cin >> s;
    int len = (int)s.size();
    
    for (int i = 0; i < len; i++)
    {
        str += '#';
        str += s[i];
    }
    str += '#';


    /*
    // 이렇게 하면 틀린다.
    for (int i = 0; i < len; i++)
    {
        str += s[i];
        str += '#';
    }
    str += '#';
    */
    
    manachers(str, (int)str.size());
    
    len = (int)str.size();
    int ans = -1;
    for (int i = 0; i < len; i++)
        ans = max(ans, A[i]);
    
    cout << ans << endl;
    
    return 0;
}