后缀自动机的模板

后缀自动机真是个好东西

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
#define ll long long
#define pb(i) push_back(i)
#define sc(x) scanf("%d",&x)
using namespace std;
const int maxn=2010000;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;
ll fpow(ll n, ll k) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n; n = n * n;} return r;}
char s[maxn];
int fa[maxn],ch[maxn][26],len[maxn],siz[maxn];
int lst=1,node=1,l,t[maxn],A[maxn];
ll ans;
void extend(int c)
{
    int f=lst,p=++node;lst=p;
    len[p]=len[f]+1;siz[p]=1;
    while(f&&!ch[f][c]) ch[f][c]=p,f=fa[f];
    if(!f){fa[p]=1;return;}
    int x= ch[f][c],y=++node;
    if(len[f]+1==len[x]){fa[p]=x;node--;return;}
    len[y]=len[f]+1;fa[y]=fa[x];fa[x]=fa[p]=y;
    memcpy(ch[y],ch[x],sizeof(ch[y]));
    while(f&&ch[f][c]==x) ch[f][c]=y,f=fa[f];
}
int main()
{
    scanf("%s",&s[1]);
    l= strlen(&s[1]);
    for(int i=1;i<=l;i++) extend(s[i]-'a');
    for(int i=1;i<=node;i++) t[len[i]]++;
    for(int i=1;i<=node;i++) t[i]+=t[i-1];
    for(int i=1;i<=node;i++) A[t[len[i]]--]=i;
    for(int i=node;i>=1;i--)
    {
        int now = A[i];siz[fa[now]]+=siz[now];
        if(siz[now]>1) ans=max(ans,1ll*siz[now]*len[now]);

    }
    printf("%lld\n",ans);
    return 0;
}