#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
typedef long long ll;
char s[MAXN];
int n,siz[MAXN<<1];
ll ans=0;
const int inf=1e8;
struct SuffixTree{
int link[MAXN<<1],len[MAXN<<1],start[MAXN<<1],s[MAXN<<1];
int n,tail,now,rem,ch[MAXN<<1][27];
SuffixTree(){tail=1,n=0,rem=0,now=1,len[0]=inf;}
int newnode(int st,int le){
link[++tail]=1;start[tail]=st;len[tail]=le;return tail;
/*build new node
link->1,start=st(have been known)
len->le have been known
tail is the new number*/
}
void Extend(int x){
s[++n]=x;rem++;
/*add len(n),add rem
n->all strings‘ number
rem->now length(not the waited suffixstrings
suffixstrings is showed by "rem" & "now"
start[u]&len[u]:
is meaning of u‘s father is s[start[u]->start[u]+len[u]-1]*/
for(int last=1;rem;){
while(rem>len[ch[now][s[n-rem+1]]])
rem-=len[now=ch[now][s[n-rem+1]]];
/*
find the edge which the head is s[n-rem+1]
because that len(rem) may bigger than this edge‘s len
so we should del it‘s len and jump to the next
this is the setp2.
*/
int &v=ch[now][s[n-rem+1]];int c=s[start[v]+rem-1];
/*
v->the edge‘s last point
c->this edge‘s last character
*/
if(!v||x==c){
link[last]=now;last=now;
if(!v)v=newnode(n,inf);
/*
if there is no edge which is follow the rule
or,2 step is failed
then we should add the "suffix link"->link[last]=now,last=now
*/
else break;
/* if we find this edge is being,also
the last character have been there
it‘s meaning that we needn‘t to add now‘s character
so,we should break.
*/
}
else{
// if the last character is not being
int u=newnode(start[v],rem-1);
// build a new node,and split this edge
ch[u][c]=v;ch[u][x]=newnode(n,inf);
/*
u->have two points:one is v->inherit the before
and the other one is x:insert x.
*/
start[v]+=rem-1;len[v]-=rem-1;
/*
also,because we split this road
v‘s start and len should be updated
start+=rem-1,also the len[v] should cut rem-1
*/
link[last]=v=u;last=u;
//build lead to update the suffix link.
}
if(now==1)rem--;
/*
root is 1
if now=1,rem should be less
*/
else now=link[now];
/*
else,in order to add the next character,we should jump to the now‘s suffix link.
the meaning of suffix link is making find the next right edge and updating it more convenient and faster.
*/
}
}
}sft;
int dfs(int u,int dep){
if(dep>=inf)return 1;
siz[u]=0;
for(int i=0;i<=26;++i){
if(sft.ch[u][i]){
/*
if we can jump this edge
then,we continue to dfs and update the siz
*/
int d=dfs(sft.ch[u][i],dep+sft.len[sft.ch[u][i]]);
siz[u]+=d;
}
}
if(siz[u]>=2)ans=max(ans,1LL*siz[u]*dep);//the problem‘s querying
return siz[u];
}
int main(){
scanf("%s",s+1);
int n=strlen(s+1);
for(int i=1;i<=n;++i)s[i]-=‘a‘,sft.Extend(s[i]);//Extend the string
sft.Extend(26);//End character
dfs(1,0);//add up the answer
printf("%lld\n",ans);
}
\(\text{The code has explained by English.And the explaining will be updated after the High school entrance examination}\)
原文:https://www.cnblogs.com/h-lka/p/13191105.html