如题所示，这是一道模板题。
事实上，尽管后缀自动机有着较为强大和完整的功能，但它的实现却是比较简单的。
概括地说，后缀自动机是一种用线性的时间复杂度和字符数与字符集的乘积的空间复杂度来储存一个字符串里每一个前缀的所有后缀，并且相同的字符串只会被表达一次的一类自动机。
下面我们考虑如何构造这个自动机。
构造后缀自动机使用的是一种被称为「增量算法」的构造方法。这种构造方法将所有的节点依次加入自动机。
后缀自动机由以下四个部分组成：
根节点，前缀节点，父亲边和字符边。
根节点一开始就存在，它象征着空串。而每一次加入的是一个前缀节点。
前缀节点表示的是原串中的某一个前缀。
每个前缀节点都有一条父亲边连向另一个节点。
每个前缀节点都有数条字符边连向另一些节点。
对于每个前缀节点，它储存的都是一些字符串。
具体而言，是这个点表示的最长串的所有长度严格大于它的父亲的最长串的长度的后缀。考虑到这个性质，每个点事实上不必记录整个字符串集合，而只需记录字符串的最长长度即可。
从这个节点沿着父亲边走到根的路径上的所有点表示的字符串集合构成的新集合，不重复不遗漏地表示了当前点的所有后缀。
我们记录一个节点nw，表示的是当前插入最长的一个前缀所在的点。
当我们加入了一个新的字符c，我们进行如下判断和操作。
新建一个点np，然后沿着nw到根的路径向上搜索，对路径上的每个点进行判断，如果这个点没有拉出过字符为c的边，就将它连一条字符为c的边连向新点。否则进行如下特殊处理。
如果沿着nw到根的每一个点都连向了新点，则表示新节点表示的每一个非空后缀都无法在已有的自动机内找到，那么它的后缀序列需要且仅需要两个点来表达：它本身，以及象征空字符串的根节点。
否则，我们考虑这个已经有字符为c的边的点，我们令它为p，它通过c连向的点为q。很明显这意味着，np代表的后缀集合与q代表的后缀集合有交集。
仍然是分类讨论。如果q表示的字符串数量是1的话，那么它代表的后缀集合显然一定是np代表的后缀集合的一个真子集。并且这个集合关于np代表的后缀集合的补集正好是np代表的字符串集合。
那么我们就可以把np的父亲边连向q。
如果q表示的字符串数量大于1，这就意味着两者的后缀集合含有交际并且互不包含。
于是我们需要把q节点拆成q和nq两个节点，其中nq表示被np包含的字符串集合，而q表示不被np包含的字符串集合。
显然需要修改字符边c的点只有p到根的路径上的所有点。因为只有这些点才能够拉出被np包含的字符串集合。
当然，这些需要修改c的点也一定是一段连续的区间。这由每个点包含的后缀集合不重复不遗漏可以得到。
而q与np的父亲都应该修改到点nq，这也很显然，因为拆点后q表示的后缀集合包含nq表示的后缀集合。
同时，原来的q点的字符出边也都应该复制到nq上。这是因为一个字符出边表示的是目的点包含了所有出发点所包含的每一个字符串末尾添上字符边代表的字符所构成的集合。
故而拆点前的q点给其他的点贡献的一部分字符串的字符出边的出发点在拆点后变成了nq。
这就完成了后缀自动机的构建。
对于这一题，我们考虑一个显而易见的性质：
一个子串在原串中出现的次数，等价于以它作为后缀的前缀个数。
因此，只要计算父亲边构成的树上的子树大小乘以节点最长字符串长度的最值即可。
#include<iostream>
#include<cstdio>
#include<cstring>
inline long long Max(long long A,long long B){
return A>B?A:B;
}
int n;
int l[2000005],fa[2000005],nxt[2000005][26],sz[2000005];
int h[2000005],v[2000005],to[2000005];
char ch[2000005];
int cnt,nw,et;
inline void add(int U,int V){
++et,v[et]=V,to[et]=h[U],h[U]=et;
}
inline void prpr(){
l[0]=0,fa[0]=-1,sz[0]=0;
cnt=nw=0;
}
int p,q,np,nq;
inline void psh(int c){
np=++cnt,p=nw,l[np]=l[nw]+1,sz[np]=1,nw=np;
while(p>=0&&!nxt[p][c]){
nxt[p][c]=np;
p=fa[p];
}
if(p==-1){
fa[np]=0;
return;
}
q=nxt[p][c];
if(l[p]+1==l[q]){
fa[np]=q;
return;
}
nq=++cnt;
for(int i=0;i<26;++i){
nxt[nq][i]=nxt[q][i];
}
fa[nq]=fa[q],fa[q]=fa[np]=nq,l[nq]=l[p]+1;
while(p>=0&&nxt[p][c]==q){
nxt[p][c]=nq;
p=fa[p];
}
}
long long ans=0;
inline void dfs(int X){
for(int i=h[X];i;i=to[i]){
dfs(v[i]);
sz[X]+=sz[v[i]];
}
if(sz[X]>1){
ans=Max(ans,1ll*sz[X]*l[X]);
}
}
void init(){
std::cin>>ch+1;
n=strlen(ch+1);
for(int i=1;i<=n;++i){
psh(ch[i]-'a');
}
for(int i=1;i<=cnt;++i){
add(fa[i],i);
}
dfs(0);
printf("%lld",ans);
}
int main(){
prpr();
init();
return 0;
}