1089 最长回文子串 V2（Manacher算法）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e6+10;
char s[N],S[N];
int l,p[N];
inline int manacher(){
    int ans=0,id=0,mx=-1;
    for(int i=1;i<l;i++){
        if(id+mx>i) p[i]=min(p[id*2-i],id+mx-i);
        while(i-p[i]-1>=0&&i+p[i]+1<=l&&S[i-p[i]-1]==S[i+p[i]+1]) p[i]++;
        if(i+p[i]>id+mx) id=i,mx=p[i];
        ans=max(ans,p[i]);
    }
    return ans;
}
int main(){
    scanf("%s",s);
    l=-1;
    memset(S,0,sizeof S);
    memset(p,0,sizeof p);
    int len=strlen(s);
    for(int i=0;i<len;i++) S[++l]=‘#‘,S[++l]=s[i];
    S[++l]=‘#‘;
    printf("%d\n",manacher());
    return 0;
}