Description
考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出 现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最
大出现值。 Input输入只有一行，为一个只包含小写字母(a -z)的非空字符串s。 Output
输出一个整数，为逝查回文子串的最大出现值。
解法一【manacher+后缀数组】见【这里】。
解法三【pam】见【这里】。
manacher找出来本质不同的回文串【 O(n) 个】然后到SAM上查询出现次数。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
char s[600010];
int fa[600010][22],trans[600010][27],val[600010],
cnt[600010],num[600010],ord[600010],
pos[600010],f[600010],
n,tot=1;
int main()
{int p,q,np,nq,last=1,c,id,mx;LL ans=1;scanf("%s",s+1);n=strlen(s+1);for (int i=1;i<=n;i++){p=last;val[last=np=++tot]=val[p]+1;c=s[i]-'a'+1;while (p&&!trans[p][c]){trans[p][c]=np;p=fa[p][0];}if (!p) fa[np][0]=1;else{q=trans[p][c];if (val[q]==val[p]+1) fa[np][0]=q;else{val[nq=++tot]=val[p]+1;fa[nq][0]=fa[q][0];fa[q][0]=fa[np][0]=nq;for (int j=1;j<=26;j++) trans[nq][j]=trans[q][j];while (p&&trans[p][c]==q){trans[p][c]=nq;p=fa[p][0];}}}}p=1;for (int i=1;i<=n;i++){p=trans[p][s[i]-'a'+1];pos[i]=p;cnt[p]++;}for (int i=1;i<=tot;i++) num[val[i]]++;for (int i=1;i<=n;i++) num[i]+=num[i-1];for (int i=1;i<=tot;i++) ord[num[val[i]]--]=i;for (int i=tot;i;i--) cnt[fa[ord[i]][0]]+=cnt[ord[i]];for (int k=1;(1<<k)<=tot;k++)for (int i=1;i<=tot;i++)fa[i][k]=fa[fa[i][k-1]][k-1];for (int i=n;i;i--){s[i*2-1]=s[i];s[i*2-2]='$';}s[2*n]='$';id=mx=0;for (int i=1;i<=n*2-1;i++){if (i<=mx) f[i]=min(mx-i,f[2*id-i]);while (i-f[i]-1>=0&&s[i+f[i]+1]==s[i-f[i]-1]) f[i]++;for (int j=mx-i+2;j<=f[i];j+=2){p=pos[(i+1)/2+j/2];for (int k=20;k>=0;k--)if (val[fa[p][k]]>=j)p=fa[p][k];ans=max(ans,(LL)cnt[p]*j);}if (i+f[i]>mx){id=i;mx=i+f[i];}}printf("%lld\n",ans);
}