Manacher 代码贴贴

#include<bits/stdc++.h>
using namespace std;
const int N=1.1e7+5;
char rS[N];
char S[N<<1];
int P[N<<1],n;
void init(){n=strlen(rS);int k=0;S[k++]='$';S[k++]='#';for(int i=0;i<n;i++){S[k++]=rS[i];S[k++]='#';}S[k++]='&';n=k;
}
int manacher(){int ans=1,mx=0,mxid=0;for(int i=1;i<n;i++){if(i<mx)P[i]=min(mx-i,P[2*mxid-i]);else P[i]=1;while(S[i+P[i]]==S[i-P[i]])P[i]++;if(P[i]+i>mx)mx=P[i]+i,mxid=i;ans=max(ans,P[i]);}return ans-1;
}
signed main(){scanf("%s",rS);init();printf("%d",manacher());return 0;
}