题意
关于回文自动机的讲解见这里
由于回文串个数是\(O(n)\)的,直接回文自动机上统计并比较即可。
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3*1e5+10;
int n;
ll ans;
char s[maxn];
struct PA
{
int tot,last;
int fail[maxn],len[maxn],cnt[maxn];
int ch[maxn][30];
inline void init()
{
fail[0]=1;
len[0]=0;len[1]=-1;
tot=1;last=0;
}
inline int getfail(int x,int n)
{
while(s[n-len[x]-1]!=s[n])x=fail[x];
return x;
}
inline void build(char* s,int n)
{
s[0]='#';
for(int i=1;i<=n;i++)
{
int p=getfail(last,i);
if(!ch[p][s[i]-'a'])
{
int q=++tot;len[q]=len[p]+2;
fail[q]=ch[getfail(fail[p],i)][s[i]-'a'];
ch[p][s[i]-'a']=q;
}
cnt[last=ch[p][s[i]-'a']]++;
}
}
}pa;
int main()
{
scanf("%s",s+1);n=strlen(s+1);
pa.init();pa.build(s,n);
for(int i=pa.tot;i;i--)pa.cnt[pa.fail[i]]+=pa.cnt[i];
for(int i=1;i<=pa.tot;i++)ans=max(ans,1ll*pa.cnt[i]*pa.len[i]);
printf("%lld",ans);
return 0;
}