【模板】最长回文串长度 manacher

\(pa_i\) 表示以 \(i\) 为中心的（原串的）回文串长度

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int n,m,pa[22000010];
char buf[11000010],a[22000010];
void manacher(char *a){
    int len=strlen(a+1);
    for(int i=1,mid=0,r=0;i<=len;i++){
        if(i<=r) pa[i]=min(pa[mid*2-i],r-i);
        while(a[i-pa[i]-1]==a[i+pa[i]+1]) pa[i]++;
        if(i+pa[i]>r) r=i+pa[mid=i]; 
    }
}
int main(){
//  #ifdef LOCAL
//      freopen("input.in","r",stdin);
//  #endif
    scanf("%s",buf+1),n=strlen(buf+1);
    a[0]='~',a[m=1]='|';
    for(int i=1;i<=n;i++) a[++m]=buf[i],a[++m]='|';
    a[++m]=0;
    printf("%d\n",manacher(a));
    return 0;
}