后缀自动机，是一种数据结构，是由状态和转移关系构成的。它虽然叫做后缀自动机，可是他却与后缀并没有什么太大的联系。
后缀自动机的每一种状态都是原串的一些子串的集合，每个子串只唯一存在于某个状态中，对每一个字符串，有一个唯一的SAM与其对应。
后缀自动机有一个叫做Right的数组，它所代表的意义是：当前可识别位置的端点的个数，它长得很像后缀数组。此外，每个状态还有一个max和min值，表示len值可以取的最大值和最小值，但通常，我们不储存min值，因为对于一个状态的min他等于它的parent的max值+1。
每个状态的max值是这个状态所包含的最大的子串的长度，min值是其最小子串的长度。
后缀自动机会生成一个叫做parent树的东西，他是原串的反串的后缀树，在后缀树上dfs一边，就能获得后缀数组。
#include#include #include const int maxn = 2000010;char S[maxn];int cnt=1,last=1,Right[maxn],tr[maxn][30],par[maxn],c[maxn],mx[maxn],n,id[maxn];void extend(int x) { int np=++cnt,p=last;Right[np]=1; mx[np]=mx[p]+1;last=np; while(p&&!tr[p][x]) tr[p][x]=np,p=par[p]; if(!p) par[np]=1; else { int q=tr[p][x]; if(mx[q]==mx[p]+1) par[np]=q; else { int nq=++cnt;mx[nq]=mx[p]+1; memcpy(tr[nq],tr[q],sizeof(tr[q])); par[nq]=par[q];par[q]=par[np]=nq; while(p&&tr[p][x]==q) tr[p][x]=nq,p=par[p]; } }}void topsort() { for(register int i=1;i<=cnt;++i) ++c[mx[i]]; for(register int i=1;i<=n;++i) c[i]+=c[i-1]; for(register int i=1;i<=cnt;++i) id[c[mx[i]]--]=i; for(register int i=cnt;i;--i) Right[par[id[i]]]+=Right[id[i]];}int main() { scanf("%s",S+1);long long ans=0; n=strlen(S+1);for(register int i=1;i<=n;++i) extend(S[i]-'a');topsort(); for(register int i=1;i<=cnt;++i) { int cur = id[i]; if(Right[cur]>1) { ans=std::max(ans,1LL*mx[cur]*Right[cur]); } } printf("%lld",ans); return 0;}