初见SAM
洛谷数据太弱了,我SAM写错了居然有90pts=。=???
SAM求一个子串$(l,r)$的出现次数:从右端点对应状态开始在parent树上倍增,当目标节点的$len$大于等于子串长度时就往上跳,最后所在节点的$len$就是该串的出现次数
于是边$manacher$边在SAM上统计当前串的出现次数即可,复杂度$O(n\log n)$,注意边界
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,K=;
int p[N],noww[N],goal[N];
int rnk[N],bkt[N],mul[N][K];
int trs[N][],fth[N],len[N],siz[N],num[N];
char str[N>>],Str[N];
int lth,lst,cnt,tot,mid,maxr;
long long ans;
void link(int f,int t)
{
noww[++cnt]=p[f];
goal[cnt]=t,p[f]=cnt;
}
void DFS(int nde,int fth)
{
mul[nde][]=fth;
for(int i=p[nde];i;i=noww[i])
DFS(goal[i],nde),siz[nde]+=siz[goal[i]];
for(int i=;mul[nde][i];i++)
mul[nde][i]=mul[mul[nde][i-]][i-];
}
void Insert(int ch,int ps)
{
int nde=lst,newn=++tot;
num[ps]=lst=newn,siz[newn]=,len[newn]=len[nde]+;
while(nde&&!trs[nde][ch])
trs[nde][ch]=newn,nde=fth[nde];
if(!nde) fth[newn]=;
else
{
int tran=trs[nde][ch];
if(len[tran]==len[nde]+)
fth[newn]=tran;
else
{
int rnde=++tot; len[rnde]=len[nde]+;
for(int i=;i<=;i++) trs[rnde][i]=trs[tran][i];
fth[rnde]=fth[tran],fth[tran]=fth[newn]=rnde;
while(nde&&trs[nde][ch]==tran)
trs[nde][ch]=rnde,nde=fth[nde];
}
}
}
void prework()
{
register int i,j;
scanf("%s",str+),lth=strlen(str+),lst=tot=;
for(i=;i<=lth;i++) Insert(str[i]-'a',i);
for(i=;i<=tot;i++) link(fth[i],i); DFS(,);
}
void Solve(int l,int r)
{
l=(l+l%)/,r=(r-r%)/;
if(l>r) return ;
int nde=num[r],lth=r-l+;
for(int i=;~i;i--)
if(lth<=len[mul[nde][i]])
nde=mul[nde][i];
ans=max(ans,1ll*lth*siz[nde]);
}
void Manacher()
{
register int i;
int newl=*lth+;
for(i=;i<=newl;i++)
Str[i]=(i&)?'?':str[i>>];
Str[]='>',Str[newl+]='<';
for(i=;i<=newl;i++)
{
fth[i]=(maxr>=i)?min(maxr-i+,fth[*mid-i]):;
Solve(i-fth[i]+,i+fth[i]-);
while(Str[i-fth[i]]==Str[i+fth[i]])
fth[i]++,Solve(i-fth[i]+,i+fth[i]-);
if(i+fth[i]->maxr) maxr=i+fth[i]-,mid=i;
}
}
int main()
{
prework(),Manacher();
printf("%lld",ans);
return ;
}