刚学后缀自动机,不熟练,有没有大佬帮帮我啊
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n , tot , lst;
ll ans = 0;
struct point{
int len , fa;
ll size;
int son[26];
point()
{
len = fa = 0;
size = 0ll;
memset(son , 0 , sizeof(son));
}
}d[1000001];
char s[1000001];
int tmp[1000001] , tp[2000001];
void sam(int now)
{
int p = lst;
int np = ++ tot;
lst = np;
d[np].size = 1;
d[np].len = d[p].len + 1;
for(; p && !d[p].son[now] ; p = d[p].fa)
d[p].son[now] = np;
if(!p)
d[np].fa = 1;
else
{
int q = d[p].son[now];
if(d[q].len == d[q].len + 1)
d[np].fa = q;
else
{
int nq = ++ tot;
d[nq] = d[q];
d[nq].size = 0;
d[nq].len = d[p].len + 1;
d[q].fa = nq;
d[np].fa = nq;
for(; p && d[p].son[now] == q ; p = d[p].fa)
d[p].son[now] = nq;
}
}
}
void get_tp()
{
for(int i = 0 ; i <= n ; i ++)
tmp[i] = 0;
for(int i = 1 ; i <= tot ; i ++)
tmp[d[i].len] ++;
for(int i = 1 ; i <= n ; i ++)
tmp[i] += tmp[i - 1];
for(int i = 1 ; i<= tot ; i ++)
tp[tmp[d[i].len] --] = i;
}
void dp()
{
for(int i = tot ; i >= 1 ; i --)
{
int now = tp[i];
d[d[now].fa].size += d[now].size;
}
for(int i = 1 ; i <= tot ;i ++)
if(d[i].size > 1)
ans = max(ans , d[i].size * d[i].len);
}
int main()
{
scanf("%s" , s + 1);
n = strlen(s + 1);
tot = lst = 1;
for(int i = 1 ; i <= n ;i ++)
sam(s[i] - 'a');
get_tp();
dp();
printf("%lld\n" ,ans);
return 0;
}