洛谷 3804 【模板】后缀自动机

题目：https://www.luogu.org/problemnew/show/P3804

学习材料：https://blog.csdn.net/qq_35649707/article/details/66473069

　　　　　https://wenku.baidu.com/view/90f22eec551810a6f4248606.html

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e6+5,M=N<<1,K=30;
int cnt=1,go[M][K],fa[M],siz[M],l[M],lst=1;//=1
int tx[N],a[M];char ch[N];
ll Mx(ll a,ll b){return a>b?a:b;}
void add(int w)
{
  int p=lst,np=++cnt;lst=np;l[np]=l[p]+1;
  for(;p&&!go[p][w];p=fa[p])go[p][w]=np;
  if(!p)fa[np]=1;// 1 not 0
  else
    {
      int q=go[p][w];
      if(l[q]==l[p]+1)fa[np]=q;
      else
    {
      int nq=++cnt; l[nq]=l[p]+1;
      fa[nq]=fa[q]; fa[q]=nq; fa[np]=nq;
      memcpy(go[nq],go[q],sizeof go[q]);
      for(;go[p][w]==q;p=fa[p])go[p][w]=nq;
    }
    }
  siz[np]=1;
}
int main()
{
  scanf("%s",ch);int n=strlen(ch);
  for(int i=0;i<n;i++)add(ch[i]-'a'+1);
  for(int i=1;i<=cnt;i++)tx[l[i]]++;
  for(int i=1;i<=n;i++)tx[i]+=tx[i-1];
  for(int i=1;i<=cnt;i++)a[tx[l[i]]--]=i;
  ll ans=0;
  for(int i=cnt;i;i--)
    {
      int d=a[i]; siz[fa[d]]+=siz[d];
      if(siz[d]>1)ans=Mx(ans,(ll)siz[d]*l[d]);
    }
  printf("%lld
",ans);
  return 0;
}