P3804 【模板】后缀自动机

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 2e6+5;
 4 typedef long long ll;
 5 char s[maxn];
 6 int a[maxn], c[maxn], size[maxn], n;
 7 ll ans = 0;
 8 struct SuffixAutoMaton {
 9     int last, cnt;
10     int ch[maxn*2][26], fa[maxn*2], len[maxn*2];
11     void ins(int c) {
12         int p = last, np = ++cnt;
13         last = np; len[np] = len[p]+1;
14         for (;p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
15         if (!p) fa[np] = 1;
16         else {
17             int q = ch[p][c];
18             if (len[p]+1 == len[q]) fa[np] = q;
19             else {
20                 int nq = ++cnt;
21                 len[nq] = len[p]+1;
22                 memcpy(ch[nq],ch[q],sizeof(ch[q]));
23                 fa[nq] = fa[q]; fa[q] = fa[np] = nq;
24                 for (; ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
25             }
26         }
27         size[np] = 1;
28     }
29     void build() {
30         scanf("%s",s+1);
31         int lens = strlen(s+1);
32         last = cnt = 1;
33         for (int i = 1; i <= lens; i++) ins(s[i]-‘a‘);
34     }
35     void solve() {
36         for (int i = 1; i <= cnt; i++) c[len[i]]++;
37         for (int i = 1; i <= cnt; i++) c[i] += c[i-1];
38         for (int i = 1; i <= cnt; i++) a[c[len[i]]--] = i;
39         for (int i = cnt; i; i--) {
40             int p = a[i];
41             size[fa[p]] += size[p];
42             if (size[p] > 1) ans = max(ans, 1LL*size[p]*len[p]);
43         }
44         printf("%lld\n",ans);
45     }
46 }sam;
47 int main() {
48     sam.build();
49     sam.solve();
50     return 0;
51 }