传送门
终于搞懂了这个东西，以后会多做几道后缀自动机的题的，顺便复习一下后缀数组。
这篇博客讲后缀自动机讲的很不错，推荐初学者看这篇博客学习。
后缀自动机还有很多的性质我还不是很懂，靠之后做的题来补就是了。
这道题最后的清算有两种办法，一种是重新建图dfs，比较方便，还有一种就是按长度对节点进行基数排序，结果就是par树的拓扑序列，然后倒着加。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <queue>
using namespace std;
typedef long long LL;
const int N=1e6+10;
char s[N];
struct SAM{
char *s;
int g[N*2][26],fa[N*2],last,tot,len[N*2],f[N*2];
vector<int> tr[N*2];
LL ans;
int newnode(){++tot;memset(g[tot],0,sizeof(g[tot]));fa[tot]=len[tot]=0;return tot;}
void add(int c){
int p=last,np=last=newnode();
len[np]=len[p]+1;f[np]=1;
for(;p&&!g[p][c];p=fa[p]) g[p][c]=np;
if(!p) fa[np]=1;
else{
int q=g[p][c];
if(len[q]==len[p]+1) fa[np]=q;
else{
int nq=newnode();memcpy(g[nq],g[q],sizeof(g[nq]));fa[nq]=fa[q];
len[nq]=len[p]+1;
fa[q]=fa[np]=nq;
for(;p&&g[p][c]==q;p=fa[p]) g[p][c]=nq;
}
}
}
void dfs(int u){
for(int v:tr[u]) dfs(v),f[u]+=f[v];
if(f[u]>1) ans=max(ans,1ll*f[u]*len[u]);
}
void init(char *_s){
s=_s;last=newnode();
for(int i=1;s[i]!=' ';i++) add(s[i]-'a');
for(int i=2;i<=tot;i++) tr[fa[i]].push_back(i);
dfs(1);
}
}sam;
int main(){
scanf("%s",s+1);
sam.init(s);
printf("%lld
",sam.ans);
return 0;
}