Description
考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出 现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最
大出现值。 Input输入只有一行，为一个只包含小写字母(a -z)的非空字符串s。 Output
输出一个整数，为逝查回文子串的最大出现值。
解法一【manacher+sa】见【这里】。
解法二【manacher+sam】见【这里】。
PAM出现以后，这题就成了裸体。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
char s[300010];
int trans[600010][30],fa[600010],val[600010],cnt[600010],n,tot;
int main()
{int p,np,last,q,c;LL ans=0;scanf("%s",s+1);n=strlen(s+1);tot=1;last=0;fa[0]=fa[1]=1;val[1]=-1;for (int i=1;i<=n;i++){c=s[i]-'a'+1;p=last;while (s[i-val[p]-1]!=s[i]) p=fa[p];if (!trans[p][c]){val[np=++tot]=val[p]+2;q=fa[p];while (s[i-val[q]-1]!=s[i]) q=fa[q];fa[np]=trans[q][c];trans[p][c]=np;}cnt[last=trans[p][c]]++;}for (int i=tot;i;i--){cnt[fa[i]]+=cnt[i];ans=max(ans,(LL)val[i]*cnt[i]);}printf("%lld\n",ans);
}