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
*/