洛谷传送门
这是一道后缀自动机的模板题,这道题让我切身体会到了后缀自动机的方便与好写。
代码如下:
#include<bits/stdc++.h>
#define N 2000005
#define ll long long
using namespace std;
char s[N];
int a[N],siz[N],n,tot[N],root=1;
ll ans=0;
struct suf{
int last,cnt,ch[N<<1][26],fa[N<<1],len[N];
inline void build(){
scanf("%s",s+1),last=cnt=1;
int l=strlen(s+1);
for(int i=1;i<=l;++i)insert(s[i]-'a');
}
inline void solve(){
for(int i=1;i<=cnt;++i)++tot[len[i]];
for(int i=1;i<=cnt;++i)tot[i]+=tot[i-1];
for(int i=1;i<=cnt;++i)a[tot[len[i]]--]=i;
for(int i=cnt;i;--i){
int p=a[i];
siz[fa[p]]+=siz[p];
if(siz[p]>1)ans=max(ans,1ll*len[p]*siz[p]);
}
printf("%lld",ans);
}
inline void insert(int c){
int p=last,newp=++cnt;
last=newp,len[newp]=len[p]+1;
for(;p&&!ch[p][c];p=fa[p])ch[p][c]=newp;
if(!p)fa[newp]=root;
else{
int q=ch[p][c];
if(len[p]+1==len[q])fa[newp]=q;
else{
int newq=++cnt;
len[newq]=len[p]+1;
memcpy(ch[newq],ch[q],sizeof(ch[q]));
fa[newq]=fa[q],fa[q]=fa[newp]=newq;
for(;ch[p][c]==q;p=fa[p])ch[p][c]=newq;
}
}
siz[newp]=1;
}
}sam;
int main(){
sam.build();
sam.solve();
return 0;
}