Algorithm/SuffixAutomaton.cpp at master · Denverjin/Algorithm · GitHub

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
88
89
90
91
92
93
94
95
96
97
98
// Code by Denverjin.
#include<bits/stdc++.h>
usingnamespacestd;

#definelddouble
#definelllonglong
#definepii pair <int, int>
#defineullunsignedlonglong
#defineF first
#defineS second
#definePB push_back
#defineMP make_pair
#definerep(i, n) for (int i = 0; i < (int)(n); ++ i)

#definePIacos(-1)
#defineMOD1000000007
#defineMUL19260817
#defineEPS1e-10
#defineINF1e9
#defineLINF1e18

template <typename T> inlinevoidchkmin(T &x, T y) {if (y < x) x = y;}
template <typename T> inlinevoidchkmax(T &x, T y) {if (y > x) x = y;}
template <typename T> inline T add(T x, T y) {return (x + y) % MOD;}
template <typename T> inline T mul(T x, T y) {return1LL * x * y % MOD;}
template <typename T> inline T qp(T x, T n) {
	T ans = 1;
do {if (n & 1) ans = mul(ans, x); x = mul(x, x);} while (n >>= 1);
return ans;
}

#ifndef DEBUG
constintSZ = 1 << 13;
char buff[SZ], *pos = buff + SZ - 1;
#definegetchar() (++ pos == buff + SZ ? fread(pos = buff, 1, SZ, stdin), *pos : *pos)
#endif

inline ll read() {
	ll x = 0; int f = 1, c = getchar();
for (;!isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x<<3) + (x<<1) + (c^48);
return x * f;
}

namespaceSAM {
staticconstint N = 1 << 22;
int tot, lst, go[N][26], link[N], len[N], tms[N];
voidinit() {
 tot = lst = 1;
memset(go, 0, sizeof go);
	}
voidadd(int c) {
int p = lst, np = ++ tot; lst = np;
 len[np] = len[p] + 1;
while (p && !go[p][c]) go[p][c] = np, p = link[p];
if (!p) link[np] = 1;
else {
int q = go[p][c];
if (len[q] == len[p] + 1) link[np] = q;
else {
int nq = ++ tot;
 len[nq] = len[p] + 1; link[nq] = link[q];
memcpy(go[nq], go[q], sizeof go[q]);
 link[np] = link[q] = nq;
while (go[p][c] == q) go[p][c] = nq, p = link[p];
 }
 }
// printf("%d\n", np);
 tms[np] = 1;
	}
}

int cnt[SAM :: N], v[SAM :: N];

intmain() {
SAM :: init();
char c = getchar();
while (!isspace(c)) {
SAM :: add(c - 'a');
 c = getchar();
	}
//	for (int i = 1; i <= SAM :: tot; ++ i) {
// printf("%d: ", i);
// rep(j, 26) printf("%d ", SAM :: go[i][j]);
// printf("link: %d\n", SAM :: link[i]);
//	}
	ll ans = 0;
for (int i = 1; i <= SAM :: tot; ++ i) cnt[SAM :: len[i]] ++;
for (int i = 1; i < SAM :: N; ++ i) cnt[i] += cnt[i - 1];
for (int i = SAM :: tot; i; -- i) v[cnt[SAM :: len[i]] --] = i;
for (int i = SAM :: tot; i; -- i) {
int p = v[i];
SAM :: tms[SAM :: link[p]] += SAM :: tms[p];
if (SAM :: tms[p] > 1) chkmax(ans, 1LL * SAM :: tms[p] * SAM :: len[p]);
	}
printf("%lld\n", ans);
return0;
}