题意：考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出现值”为t在s中的出现次数乘以t的长度。
请你求出s的所有回文子串中的最大出现值。
len<=300000
思路：
做法一：manacher+Trie
鸣谢UOJ上ID为nothing100的小哥（小姐姐？）
学P一时爽，转C火葬场
考虑不同的回文子串中间也是有子串关系的，并且互不包含的极长回文子串的数量是O（n）级别的
所以可先用manacher算出每个位置的最长回文半径
将它们表示成一棵树的形状，一个节点的儿子是它所代表的子串向两侧扩展一个相同字母的串
判断是否是父子关系可以用hash
最后dfs一遍求子树大小就行了，注意需要双hash，C党hash后可以用map和makepair
讲道理C党到这里就能做了，问题我是P党
考虑到刚才那棵树，如果你每个串都只取后半段，那么它是一颗Trie树
所以可以用和刚才类似的方法，而且并不需要hash
manacher过程中
i关于id的对称中心j，mx>i时：
如果p[j]>mx-i则p[i]需要从p[j]开始退格，依次删除最后一个字符直到到达mx-i为止
否则p[i]即为p[j]
mx<=i时说明当前只有i一个字符，就从头开始扩展
UOJ上过了，BZ上没过，残念……
var map:array[..,..]of longint;
fa,size,p,f,a,h:array[..]of longint;
n,m,i,j,mx,id,cnt,len:longint;
ans:int64;
ch:char; function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end; function max(x,y:int64):int64;
begin
if x>y then exit(x);
exit(y);
end; function get(x,y:longint):longint;
begin
if map[x,y]= then
begin
inc(cnt);
fa[cnt]:=x;
map[x,y]:=cnt;
end;
exit(map[x,y]);
end; procedure dfs(u,ch:longint;dep:int64);
var i,v:longint;
begin
for i:= to do
begin
v:=map[u,i];
if v> then
begin
dfs(v,i,dep+);
size[u]:=size[u]+size[v];
end;
end;
if ch< then ans:=max(ans,dep*size[u]);
end; begin
assign(input,'bzoj3676.in'); reset(input);
assign(output,'bzoj3676.out'); rewrite(output); n:=; a[]:=; a[]:=;
while not eoln do
begin
read(ch);
inc(n); a[n]:=ord(ch)-ord('a')+;
inc(n); a[n]:=;
end;
inc(n); a[n]:=;
mx:=; id:=; cnt:=;
for i:= to n- do
begin
if mx>i then
begin
p[i]:=p[id*-i]; h[i]:=h[id*-i];
if p[i]>mx-i then
begin
for j:=p[i]- downto mx-i do h[i]:=fa[h[i]];
p[i]:=mx-i;
end;
end
else
begin
h[i]:=get(,a[i]);
p[i]:=;
end;
while a[i-p[i]]=a[i+p[i]] do
begin
h[i]:=get(h[i],a[i-p[i]]);
inc(p[i]);
end;
if p[i]+i>mx then
begin
mx:=p[i]+i; id:=i;
end;
inc(size[h[i]]);
end;
dfs(,,);
writeln(ans);
close(input);
close(output);
end.
做法2：回文自动机板子
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> Pll;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef pair<ll,int>P;
#define N 300010
#define M 210000
#define fi first
#define se second
#define MP make_pair
#define pi acos(-1)
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define lowbit(x) x&(-x)
#define Rand (rand()*(1<<16)+rand())
#define id(x) ((x)<=B?(x):m-n/(x)+1)
#define ls p<<1
#define rs p<<1|1 const int MOD=,inv2=(MOD+)/;
double eps=1e-;
int INF=<<;
ll inf=5e13;
int dx[]={-,,,};
int dy[]={,,-,}; char s[N];
int n; struct pam
{
int q,p,id,cnt[N],num[N],f[N],len[N],t[N][]; pam()
{
id=; f[]=f[]=; len[]=-;
} void add(int x,int n)
{
while(s[n-len[p]-]!=s[n]) p=f[p];
if(!t[p][x])
{
int q=++id,k=f[p];
len[q]=len[p]+;
while(s[n-len[k]-]!=s[n]) k=f[k];
f[q]=t[k][x];
t[p][x]=q;
num[q]=num[f[q]]+;
}
p=t[p][x];
cnt[p]++;
} void solve()
{
ll ans=;
per(i,id,)
{
cnt[f[i]]+=cnt[i];
ans=max(ans,1ll*cnt[i]*len[i]);
}
printf("%lld\n",ans);
} }pam; int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} int main()
{
//freopen("1.in","r",stdin); scanf("%s",s+);
n=strlen(s+);
rep(i,,n) pam.add(s[i]-'a',i);
pam.solve();
return ;
}
