https://www.lydsy.com/JudgeOnline/problem.php?id=3676
回文自动机模板题
4年前的APIO如今竟沦为模板,,,╮(╯▽╰)╭,唉
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std; #define N 300001 char ss[N];
int s[N]; int tot=,last;
int fail[N],len[N],cnt[N];
int tr[N][];
int p,c,np,t; void extend(int i)
{
p=last; c=s[i];
while(s[i--len[p]]!=c)
p=fail[p];
if(!tr[p][c])
{
np=++tot;
len[np]=len[p]+;
t=fail[p];
while(s[i--len[t]]!=c) t=fail[t];
fail[np]=tr[t][c];
tr[p][c]=np;
}
else np=tr[p][c];
cnt[last=np]++;
} int main()
{
scanf("%ss",ss+);
int n=strlen(ss+);
s[]=-;
for(int i=;i<=n;++i) s[i]=ss[i]-'a';
fail[]=; len[]=-;
for(int i=;i<=n;++i)
extend(i);
for(int i=tot;i>;--i) cnt[fail[i]]+=cnt[i];
long long ans=;
for(int i=;i<=tot;++i) ans=max(ans,1LL*cnt[i]*len[i]);
printf("%lld",ans);
}