题目大意：
给你一个字符串，求其中回文子串的长度*出现次数的最大值
明明是PAM裸题我干嘛要用SAM做
回文子串有一个神奇的性质，一个字符串本质不同的回文子串个数是$O(n)$级别的
用$manacher$的思想分析一下，$maxright$指针向右扩展才会产生新的回文串
其它的回文串都根据之前求得的信息得到的，比如根据回文中心对称，或者是不超过当前最长回文上限
每次扩展成功时，都把这个回文串放到$SAM$里跑
预处理出每个前缀结尾在$SAM$里的节点编号，就不用每次都从头跑了
沿着$pre$指针倍增地往上跳，直到跳到当前节点能表示出这个回文串为止
注意长度为1的串的情况
如果被卡空间了，会发现预处理以后，trs指针没什么用了，把它当成倍增的数组吧
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N1 305000
#define S1 (N1<<1)
#define T1 (N1<<2)
#define ll long long
#define uint unsigned int
#define rint register int
#define dd double
#define il inline
#define inf 0x3f3f3f3f
#define idx(X) (X-'a')
using namespace std; int gint()
{
int ret=,fh=;char c=getchar();
while(c<''||c>''){if(c=='-')fh=-;c=getchar();}
while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}
return ret*fh;
}
int n,m,len;
/*struct Edge{
int head[S1],to[S1],nxt[S1],cte;
void ae(int u,int v){
cte++;to[cte]=v,nxt[cte]=head[u],head[u]=cte;}
}E;*/
namespace SAM{
int trs[S1][],pre[S1],dep[S1],ed[S1],pos[S1],la,tot;
void init(){tot=la=;}
void insert(int c,int id)
{
int p=la,np=++tot,q,nq;la=np;
dep[np]=dep[p]+;
pos[id]=np,ed[np]=;
for(;p&&!trs[p][c];p=pre[p]) trs[p][c]=np;
if(!p) {pre[np]=;return;}
q=trs[p][c];
if(dep[q]==dep[p]+) pre[np]=q;
else{
pre[nq=++tot]=pre[q];
pre[q]=pre[np]=nq;
dep[nq]=dep[p]+;
memcpy(trs[nq],trs[q],sizeof(trs[q]));
for(;p&&trs[p][c]==q;p=pre[p]) trs[p][c]=nq;
}
}
int hs[S1],que[S1],sz[S1];
//int ff[S1][20];
void build()
{
int i,j,x;
for(i=;i<=tot;i++) hs[dep[i]]++;
for(i=;i<=n;i++) hs[i]+=hs[i-];
for(i=;i<=tot;i++) que[hs[dep[i]]--]=i;
for(i=tot;i;i--)
{
x=que[i];//E.ae(pre[x],x);
if(ed[x]) sz[x]++;
sz[pre[x]]+=sz[x];
trs[x][]=x,trs[x][]=pre[x];
}
for(j=;j<=;j++)
for(i=;i<=tot;i++)
trs[i][j]=trs[ trs[i][j-] ][j-];
}
int solve(int x,int s,int e)
{
int fx,L=e-s+;
for(int j=;j>=;j--)
//for(int j=5;j>=0;j--)
{
if(!trs[x][j]) continue;
fx=trs[x][j];
if(dep[fx]>=L) x=fx;
}
return sz[x];
}
};
char str[N1],man[S1];
int p[S1],hs[]; int main()
{
//freopen("t1.in","r",stdin);
scanf("%s",str+);
n=strlen(str+);
man[]='$',man[]='#';
int i,j,mr=,mid=,l,r,x;
SAM::init();
for(i=;i<=n;i++) SAM::insert(idx(str[i]),i);
SAM::build();
for(i=;i<=n;i++) man[*i]=str[i],man[*i+]='#';
p[]=;
ll ans=;
for(i=;i<=*n+;i++)
{
if(i<mr) p[i]=min(p[*mid-i],mr-i);
else p[i]=;
while(man[i-p[i]]==man[i+p[i]])
{
if(!((i+p[i])&))
{
l=(i-p[i])>>;
r=(i+p[i])>>;
x=SAM::pos[r];
ans=max(ans,1ll*(r-l+)*SAM::solve(x,l,r));
}
p[i]++;
}
if(i+p[i]>mr) mr=i+p[i],mid=i;
}
for(i=;i<=n;i++)
if(!hs[idx(str[i])])
{
hs[idx(str[i])]=;
l=i,r=i,x=SAM::pos[r];
ans=max(ans,1ll*SAM::solve(x,l,r));
}
printf("%lld\n",ans);
return ;
}
进入正题
这明明是一道$PAM$裸题嘛
$PAM$的构造方式类似于$AC$自动机..但它仍然有许多美妙的性质
比如奇回文树是树根节点深度设为-1等等...
而且$PAM$代码非常短
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N1 301000
#define S1 (N1<<1)
#define ll long long
#define uint unsigned int
#define rint register int
#define dd double
#define il inline
#define inf 0x3f3f3f3f
#define idx(X) (X-'a')
using namespace std; int gint()
{
int ret=,fh=;char c=getchar();
while(c<''||c>''){if(c=='-')fh=-;c=getchar();}
while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}
return ret*fh;
}
int n,len,cnt;
namespace PAM{
int trs[N1][],pre[N1],dep[N1],sz[N1],la,tot;
void init(){la=tot=,pre[]=pre[]=,dep[]=-;}
int ntsym(char *str,int i,int p){return str[i-dep[p]-]!=str[i]?:;}
void insert(char *str,int i)
{
int p=la,np,fp,c=idx(str[i]);
while(ntsym(str,i,p)) p=pre[p];
if(!trs[p][c])
{
np=++tot;
dep[np]=dep[p]+;
fp=pre[p];
while(ntsym(str,i,fp)) fp=pre[fp];
pre[np]=trs[fp][c];
trs[p][c]=np;
}
la=trs[p][c];
sz[trs[p][c]]++;
return;
}
ll topo()
{
ll ans=;
for(int x=tot;x>;x--)
sz[pre[x]]+=sz[x],ans=max(ans,1ll*dep[x]*sz[x]);
return ans;
}
};
char str[N1]; int main()
{
//freopen("t2.in","r",stdin);
//freopen("a.out","w",stdout);
int i;PAM::init();
scanf("%s",str+);len=strlen(str+);
for(i=;i<=len;i++) PAM::insert(str,i);
printf("%lld\n",PAM::topo());
return ;
}