Description
考虑一个只包含小写拉丁字母的字符串 \(s\) 。我们定义 \(s\) 的一个子串 \(t\) 的“出
现值”为 \(t\) 在 \(s\) 中的出现次数乘以 \(t\) 的长度。请你求出 \(s\) 的所有回文子串中的最
大出现值。
Input
输入只有一行，为一个只包含小写字母 \(a-z\) 的非空字符串 \(s\) 。
Output
输出一个整数，为逝查回文子串的最大出现值。
Sample Input
【样例输入1】
abacaba
【样例输入2】
www
Sample Output
【样例输出1】
7
【样例输出2】
4
HINT
一个串是回文的，当且仅当它从左到右读和从右到左读完全一样。
在第一个样例中，回文子串有7个：a，b，c，aba，aca，bacab，abacaba，其中：
● a出现4次，其出现值为4：1：1=4
● b出现2次，其出现值为2：1：1=2
● c出现1次，其出现值为l：1：l=l
● aba出现2次，其出现值为2：1：3=6
● aca出现1次，其出现值为1=1：3=3
●bacab出现1次，其出现值为1：1：5=5
● abacaba出现1次，其出现值为1：1：7=7
故最大回文子串出现值为7。
【数据规模与评分】
数据满足1≤字符串长度≤300000。
想法
做法一：回文树
算是模板题吧。
由于本质不同的回文串个数不超过 \(|S|\) ，我们考虑统计每个回文串出现次数。
考虑在增量建树时，每增一个点都找到了以它为结尾最长回文后缀 \(x\) 及 其 \(fail\) 值，那么加入这个点，增加的回文串就是 \(x\) 及 \(x\) 一路 \(fail\) 上去经过的所有节点。
但每增一个点都统计一遍有点慢，于是记下来最后在 \(fail\) 树上统一 \(dp\) 出答案即可。
做法二：后缀自动机+ \(manacher\)
先把字符串加到后缀自动机中，预处理 \(endpos\) 集合大小，即子串出现次数。
进行 \(manacher\) 算法时，如果 \(mx\) 往后扩展了，说明可能形成了一个本质不同的字符串，于是用后缀自动机统计它的出现次数。
在 \(parent\) 树上倍增找到该结点即可。
代码
回文树
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 300005;
typedef long long ll;
char s[N];
int n;
int cnt,fail[N],len[N],t[N],ch[N][26],last;
void init(){ fail[0]=fail[1]=1; len[1]=-1; last=cnt=1; }
void insert(int i,int c){
int p=last;
for(;s[i-len[p]-1]!=s[i];) p=fail[p];
if(ch[p][c]) { t[ch[p][c]]++;/**/ last=ch[p][c]; return; }
int x=++cnt,k=fail[p];
for(;s[i-len[k]-1]!=s[i];) k=fail[k];
fail[x]=ch[k][c];
len[x]=len[p]+2; ch[p][c]=x;
t[x]++; last=x;
}
int in[N],que[N],hd,tl;
ll ans;/**/
void cal(){
for(int i=2;i<=cnt;i++) in[fail[i]]++;
hd=tl=0;
for(int i=2;i<=cnt;i++) if(in[i]==0) que[tl++]=i;
while(hd<tl){
int x=que[hd++];
if(x==1) break;
ans=max(ans,1ll*t[x]*len[x]);
t[fail[x]]+=t[x]; in[fail[x]]--;
if(in[fail[x]]==0) que[tl++]=fail[x];
}
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
init();
for(int i=1;i<=n;i++) insert(i,s[i]-'a');
cal();
printf("%lld\n",ans);
return 0;
}