1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include<bits/stdc++.h>
using namespace std;
char c[1000001];
int n;
struct node{
int ch[26];
int len,fa;
}a[2000001];
struct edge{
int t,next;
}e[2000001];
int tot=1,last=1;
int head[2000001],cnt=0;
long long k[2000001];
inline void add(int a,int b)
{
cnt++;
e[cnt].t=b;
e[cnt].next=head[a];
head[a]=cnt;
return ;
}
inline void insert(int c)
{
int p=last;
int np=last=++tot;
k[tot]=1;
a[np].len=a[p].len+1;
for(;p&&!a[p].ch[c];p=a[p].fa)
{
a[p].ch[c]=np;
}
if(!p)
{
a[np].fa=1;
}
else
{
int q=a[p].ch[c];
if(a[q].len==a[p].len+1)
{
a[np].fa=q;
}
else
{
int nq=++tot;
a[nq]=a[q];
a[nq].len=a[p].len+1;
a[q].fa=a[np].fa=nq;
for(;p&&a[p].ch[c]==q;p=a[p].fa)
{
a[p].ch[c]=nq;
}
}
}
return ;
}
long long ans=0;
void dfs(int now)
{
for(int i=head[now];i;i=e[i].next)
{
dfs(e[i].t);
k[now]+=k[e[i].t];
}
if(k[now]!=1)
{
ans=max(ans,k[now]*a[now].len);
}
return ;
}
int main()
{
cin>>c;
n=strlen(c);
for(int i=0;i<n;i++)
{
insert(c[i]-'a');
}
for(int i=2;i<=tot;i++)
{
add(a[i].fa,i);
}
dfs(1);
cout<<ans<<endl;
return 0;
}
|