Rt,写的Manacher+SAM
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 600006
using namespace std;
struct SAM{
int len[N],fa[N],idx,pre,mat[N],T,nxt[N][26];long long sz[N];
SAM(){fa[0]=~0;idx=T=pre=len[0]=0;}
void extend(int ch){
int cur=++idx,p=pre;len[cur]=len[pre]+1;
while(~p&&!nxt[p][ch])nxt[p][ch]=cur,p=fa[p];
if(p==-1)fa[cur]=0;
else{
int q=nxt[p][ch];
if(len[p]+1==len[q])fa[cur]=q;
else{
int now=++idx;len[now]=len[p]+1;fa[now]=fa[q];
rep(i,0,25)nxt[now][i]=nxt[q][i];
fa[cur]=fa[q]=now;
while(~p&&nxt[p][ch]==q)nxt[p][ch]=now,p=fa[p];
}
}sz[mat[++T]=pre=cur]=1;
}
vector<int>a[N];
int f[N][20],t;
void dfs(int x){
f[x][0]=fa[x];
rep(i,1,t)f[x][i]=f[f[x][i-1]][i-1];
for(int i=0;i<(int)a[x].size();i++)dfs(a[x][i]),sz[x]+=sz[a[x][i]];
}
long long query(int l,int r){
//cout<<l<<" "<<r<<endl;
l=(l+1)>>1,r=r>>1;
int now=mat[r];
pre(i,t,0)if(~f[now][i]&&r-l+1<len[f[now][i]])now=f[now][i];
return sz[now];
}
void init(){t=log2(idx);rep(i,1,idx)a[fa[i]].push_back(i);dfs(0);}
}w;
char s[N],t[N];
int n,m,r[N];long long ans;
int main(){
freopen("input","r",stdin);
scanf("%s",s+1);
m=strlen(s+1);char op='z'+1;
rep(i,1,m)w.extend(s[i]-'a');
w.init();
t[0]='#';t[++n]=op;
rep(i,1,m)t[++n]=s[i],t[++n]=op;
int mx=0,mid=0;
//cout<<"ss"<<endl;
rep(i,1,n){
if(i>mx){
r[i]=1;
while(t[i+r[i]]==t[i-r[i]])ans=max(ans,1LL*w.query(i-r[i],i+r[i])*r[i]),r[i]++;
mx=i+r[i]-1,mid=i;
}
else{
r[i]=min(r[(mid<<1)-i],mx-i+1);
while(t[i+r[i]]==t[i-r[i]])ans=max(ans,1LL*w.query(i-r[i],i+r[i])*r[i]),r[i]++;
if(i+r[i]-1>mx)mx=i+r[i]-1,mid=i;
}
}
//cout<<ans<<endl;
//rep(i,1,m)ans=max(ans,w.query(i<<1,i<<1));
printf("%lld\n",ans);
return 0;
}
/*
g++ a.cpp -o a -Wall
*/