致敬gay学长的三模哈希。
不会马拉车于是用刚学的哈希$+$二分找回文子串。
一个串的本质不同的回文子串个数是$O(n)$的。
枚举回文中心，不断从两头缩减其回文子串的长度，用unordered_map判重，$SAM+$树上倍增求出现次数即可。
然而$M$了，换后缀数组$+ST$表$+$二分$WA$了。
哈希模数是unsigned long long自然溢出，加了一个unsigned int自然溢出还是$WA$，又搞了个$10^9+7$模数才过。
实际上只用unsigned long long和$10^9+7$就能过。
不过心血来潮想要致敬$gayge$下划线派系的码风还是放上以下划线个数区分的三模哈希：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <tr1/unordered_map>
#define maxn 300005
#define inf 0x3f3f3f3f
const unsigned long long base = 131;
const unsigned int _base = 137;
const int __base = 207;
const int mod = 1e9 + 7;
using namespace std;
using namespace tr1;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
int f[maxn][21],sa[maxn],rk[maxn],tp[maxn],tax[maxn],hei[maxn],lg[maxn],n,m;
unsigned long long sum[maxn],rev[maxn],pw[maxn]={1};
unsigned int _sum[maxn],_rev[maxn],_pw[maxn]={1};
int __sum[maxn],__rev[maxn],__pw[maxn]={1};
unordered_map<unsigned long long,bool>unq;
unordered_map<unsigned int,bool>_unq;
unordered_map<int,bool>__unq;
char s[maxn];
void Rsort(){
for(register int i=0;i<=m;++i)tax[i]=0;
for(register int i=1;i<=n;++i)++tax[rk[i]];
for(register int i=1;i<=m;++i)tax[i]+=tax[i-1];
for(register int i=n;i;--i)sa[tax[rk[tp[i]]]--]=tp[i];
}
void Ssort(){
for(register int i=1;i<=n;++i)rk[i]=s[i],tp[i]=i;
m=225,Rsort();
for(register int k=1,p=0;p<n;k<<=1,m=p){
p=0;
for(register int i=1;i<=k;++i)tp[++p]=n-k+i;
for(register int i=1;i<=n;++i)if(sa[i]>k)tp[++p]=sa[i]-k;
Rsort();
for(register int i=1;i<=n;++i)tp[i]=rk[i];
rk[sa[1]]=p=1;
for(register int i=2;i<=n;++i)
rk[sa[i]]=tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k]?p:++p;
}
}
void get_height(){
int k=0,x;
for(register int i=1;i<=n;++i){
if(rk[i]==1)continue;
if(k)--k;
x=sa[rk[i]-1];
while(x+k<=n&&i+k<=n&&s[i+k]==s[x+k])++k;
f[rk[i]][0]=hei[rk[i]]=k;
}
}
void ST(){
for(register int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;
for(register int j=1;j<=lg[n];++j)
for(register int i=1;i+(1<<(j-1))<=n;++i)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
inline int query(int l,int r){
int len=lg[r-l+1];
return min(f[l][len],f[r-(1<<len)+1][len]);
}
inline int lcp(int i,int j){
if(i==j)return n-i+1;
return query(min(rk[i],rk[j])+1,max(rk[i],rk[j]));
}
inline unsigned long long sec(int l,int r){return sum[r]-sum[l-1]*pw[r-l+1];}
inline unsigned long long rsec(int l,int r){return rev[l]-rev[r+1]*pw[r-l+1];}
inline unsigned int _sec(int l,int r){return _sum[r]-_sum[l-1]*_pw[r-l+1];}
inline unsigned int _rsec(int l,int r){return _rev[l]-_rev[r+1]*_pw[r-l+1];}
inline int __sec(int l,int r){return (__sum[r]-1ll*__sum[l-1]*__pw[r-l+1]%mod+mod)%mod;}
inline int __rsec(int l,int r){return (__rev[l]-1ll*__rev[r+1]*__pw[r-l+1]%mod+mod)%mod;}
int get_siz(int L,int R){
int l=1,r=rk[L],ans,mid;
while(l<r){
mid=l+r>>1;
if(lcp(sa[mid],L)>=R-L+1)r=mid;
else l=mid+1;
}
ans=l;
l=rk[L],r=n;
while(l<r){
mid=l+r+1>>1;
if(lcp(sa[mid],L)>=R-L+1)l=mid;
else r=mid-1;
}
return l-ans+1;
}
inline int rev1(int x){
int l=0,r=min(x-1,n-x),mid;
while(l<r){
mid=l+r+1>>1;
if(sec(x-mid,x)==rsec(x,x+mid)&&_sec(x-mid,x)==_rsec(x,x+mid)&&__sec(x-mid,x)==__rsec(x,x+mid))l=mid;
else r=mid-1;
}
return l;
}
inline int rev2(int x){
int l=0,r=min(x-1,n-x+1),mid;
while(l<r){
mid=l+r+1>>1;
if(sec(x-mid,x-1)==rsec(x,x+mid-1)&&_sec(x-mid,x-1)==_rsec(x,x+mid-1)&&__sec(x-mid,x-1)==__rsec(x,x+mid-1))l=mid;
else r=mid-1;
}
return l;
}
int main(){
int x,r;
scanf("%s",s+1),n=strlen(s+1);
for(register int i=1;i<=n;++i){
sum[i]=sum[i-1]*base+s[i]-'a'+1,_sum[i]=_sum[i-1]*_base+s[i]-'a'+1,__sum[i]=(1ll*__sum[i-1]*__base%mod+s[i]-'a'+1)%mod;
_pw[i]=_pw[i-1]*_base,pw[i]=pw[i-1]*base,__pw[i]=1ll*__pw[i-1]*__base%mod;
}
for(register int i=n;i;--i){
rev[i]=rev[i+1]*base+s[i]-'a'+1,_rev[i]=_rev[i+1]*_base+s[i]-'a'+1,__rev[i]=(1ll*__rev[i+1]*__base%mod+s[i]-'a'+1)%mod;
}
Ssort(),get_height(),ST();
long long ans=0;
unsigned long long has;
unsigned int _has;
int __has;
for(register int i=1;i<=n;++i){
r=rev1(i);
while(~r){
has=sec(i-r,i+r);
_has=_sec(i-r,i+r);
__has=__sec(i-r,i+r);
if(unq[has]&&_unq[_has]&&__unq[__has])break;
unq[has]=1,_unq[_has]=1,__unq[__has]=1;
ans=max(ans,1ll*get_siz(i-r,i+r)*((r<<1)+1));
--r;
}
r=rev2(i);
while(r){
has=sec(i-r,i+r-1);
_has=_sec(i-r,i+r-1);
__has=__sec(i-r,i+r-1);
if(unq[has]&&_unq[_has]&&__unq[__has])break;
unq[has]=1,_unq[_has]=1,__unq[__has]=1;
ans=max(ans,1ll*get_siz(i-r,i+r-1)*r<<1);
--r;
}
}
printf("%lld\n",ans);
}
