题目链接：http://uoj.ac/problem/103

题解：

首先，我们可以用后缀自动机算出每个字符串的出现次数。然后我们可以用manacher找出所有不同的回文串(o(n)个)，统计答案即可。

#include
     
      #include
      
       #include
       
        #define maxn 300005using namespace std;int n,tot,num[maxn<<1],ch[maxn<<1][26],fail[maxn<<1][20],len[maxn<<1],f[maxn<<1],last,pos[maxn<<1],cd[maxn<<1];char s[maxn<<1];long long ans,ans1,ans2;int depend(int x){  int p=last,np=++tot;len[np]=len[p]+1;  while(p!=-1&&!ch[p][x])ch[p][x]=np,p=fail[p][0];  if(p==-1)fail[np][0]=0;  else{    int q=ch[p][x];    if(len[q]==len[p]+1)fail[np][0]=q;    else{      int nq=++tot;len[nq]=len[p]+1;      memcpy(ch[nq],ch[q],sizeof(ch[q]));      fail[nq][0]=fail[q][0];fail[q][0]=fail[np][0]=nq;      while(p!=-1&&ch[p][x]==q)ch[p][x]=nq,p=fail[p][0];    }  }  return last=np;}int head,tail,d[maxn<<1];void bfs(){  head=1;tail=0;  for(int i=1;i<=tot;i++)if(cd[i]==0)d[++tail]=i;  while(head<=tail){    int x=d[head++];    num[fail[x][0]]+=num[x];cd[fail[x][0]]--;    if(cd[fail[x][0]]==0)d[++tail]=fail[x][0];  }}int main(){  scanf("%s",s+1);n=strlen(s+1);fail[0][0]=-1;  for(int i=1;i<=n;i++)num[pos[i]=depend(s[i]-'a')]++;  for(int i=1;i<=tot;i++)cd[fail[i][0]]++;bfs();  fail[0][0]=0;  for(int i=1;i<20;i++)    for(int j=1;j<=tot;j++)      fail[j][i]=fail[fail[j][i-1]][i-1];  int id=1,mx=1;  for(int i=n;i;i--)s[i<<1|1]='#',s[i<<1]=s[i];  s[1]='#';ans=ans1=ans2=0;  for(int i=2;i<=(n<<1);i++){    if(i<=mx)f[i]=min(mx-i+1,f[id*2-i]);    else f[i]=1;    while(i-f[i]>0&&s[i+f[i]]==s[i-f[i]])f[i]++;    for(int j=mx-i+2;j
        
         =0;k--)if(len[fail[p][k]]>=j)p=fail[p][k];      if(1LL*num[p]*j>ans)ans=1LL*num[p]*j,ans1=num[p],ans2=j;    }    if(i+f[i]-1>mx){id=i;mx=i+f[i]-1;}  }  printf("%lld\n",ans);  return 0;}