manacher(马拉车板子)

ABC398 F，一定要注意s最后和前面放的东西不一样，血泪教训

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using db = double;
#define int long long 
const int N=1e7+1e6+10;
int n,P[N<<1];
char a[N],s[N<<1];
void change(){
    n=strlen(a);
    // cout<<n<<endl;
    int k=0;
    s[k++]='$';//
    s[k++]='#';
    for(int i=0;i<n;i++){
        s[k++]=a[i];
        s[k++]='#';
    }
    s[k++]='&';//注意这个地方和第一个地方放的东西要不一样，不然如:aaaa会出现非常奇怪的大数
    n=k;
}
void manacher(){
    int R=0,C;
    for(int i=1;i<n;i++){
        if(i<R) P[i]=min(P[(C<<1)-i],P[C]+C-i);
        else P[i]=1;
        while(s[i+P[i]]==s[i-P[i]]) P[i]++;
        if(P[i]+i>R){
            R=P[i]+i;
            C=i;
        }
    }
}
signed main(){
    // std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    scanf("%s",a);
    change();
    manacher();
    int ans=1;
    for(int i=0;i<n;i++) {
        ans=max(ans,P[i]);
    }
    ans--;
    cout<<ans<<endl;
    // for(int i=0;i<n;i++){
    //     cout<<s[i]<<" "<<P[i]<<"\n";
    //  }
    return 0;
}