// And you curse yourself for things you never done
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 3e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
int f[maxn], ln[maxn];
int nxt[maxn][26];
vector<int> v[maxn];
int val[maxn];
ll ANS;
int dfs(int u){
int num = val[u];
for(int y : v[u]){
num+= dfs(y);
}
ANS = max(ANS, 1ll * num * ln[u]);
return num;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
int C = 2;
ln[0] = -1;
ln[1] = 0;
f[1] = 0;
f[0] = 0;
string s;
cin >> s;
int tmp = 1;
for(int i = 0; i < sz(s); i++){
while(i - ln[tmp] <= 0 || s[i - ln[tmp] - 1] != s[i])
tmp = f[tmp];
if(nxt[tmp][s[i] - 'a'] == 0){
ln[C] = ln[tmp] + 2;
nxt[tmp][s[i] - 'a'] = C;
int tmp2 = f[tmp];
while(i - ln[tmp2] <= 0 || s[i - ln[tmp2] - 1] != s[i])
tmp2 = f[tmp2];
if(tmp == 0)
f[C] = 1;
else
f[C] = nxt[tmp2][s[i] - 'a'];
C++;
}
tmp = nxt[tmp][s[i] - 'a'];
val[tmp]++;
}
for(int i = 1; i < C; i++){
v[f[i]].PB(i);
}
dfs(0);
return cout << ANS << endl, 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7424 KB |
Output is correct |
2 |
Correct |
6 ms |
7424 KB |
Output is correct |
3 |
Correct |
5 ms |
7456 KB |
Output is correct |
4 |
Correct |
5 ms |
7424 KB |
Output is correct |
5 |
Correct |
5 ms |
7424 KB |
Output is correct |
6 |
Correct |
5 ms |
7424 KB |
Output is correct |
7 |
Correct |
5 ms |
7424 KB |
Output is correct |
8 |
Correct |
5 ms |
7424 KB |
Output is correct |
9 |
Correct |
5 ms |
7424 KB |
Output is correct |
10 |
Correct |
6 ms |
7424 KB |
Output is correct |
11 |
Correct |
5 ms |
7424 KB |
Output is correct |
12 |
Correct |
6 ms |
7424 KB |
Output is correct |
13 |
Correct |
5 ms |
7424 KB |
Output is correct |
14 |
Correct |
6 ms |
7424 KB |
Output is correct |
15 |
Correct |
5 ms |
7424 KB |
Output is correct |
16 |
Correct |
5 ms |
7424 KB |
Output is correct |
17 |
Correct |
6 ms |
7424 KB |
Output is correct |
18 |
Correct |
5 ms |
7424 KB |
Output is correct |
19 |
Correct |
5 ms |
7424 KB |
Output is correct |
20 |
Correct |
5 ms |
7424 KB |
Output is correct |
21 |
Correct |
5 ms |
7424 KB |
Output is correct |
22 |
Correct |
5 ms |
7424 KB |
Output is correct |
23 |
Correct |
5 ms |
7424 KB |
Output is correct |
24 |
Correct |
5 ms |
7424 KB |
Output is correct |
25 |
Correct |
5 ms |
7424 KB |
Output is correct |
26 |
Correct |
5 ms |
7424 KB |
Output is correct |
27 |
Correct |
6 ms |
7424 KB |
Output is correct |
28 |
Correct |
5 ms |
7424 KB |
Output is correct |
29 |
Correct |
5 ms |
7424 KB |
Output is correct |
30 |
Correct |
6 ms |
7424 KB |
Output is correct |
31 |
Correct |
5 ms |
7424 KB |
Output is correct |
32 |
Correct |
5 ms |
7424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7552 KB |
Output is correct |
2 |
Correct |
5 ms |
7552 KB |
Output is correct |
3 |
Correct |
5 ms |
7552 KB |
Output is correct |
4 |
Correct |
6 ms |
7552 KB |
Output is correct |
5 |
Correct |
5 ms |
7552 KB |
Output is correct |
6 |
Correct |
5 ms |
7552 KB |
Output is correct |
7 |
Correct |
5 ms |
7552 KB |
Output is correct |
8 |
Correct |
6 ms |
7552 KB |
Output is correct |
9 |
Correct |
5 ms |
7552 KB |
Output is correct |
10 |
Correct |
6 ms |
7424 KB |
Output is correct |
11 |
Correct |
5 ms |
7424 KB |
Output is correct |
12 |
Correct |
5 ms |
7552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
9084 KB |
Output is correct |
2 |
Correct |
7 ms |
9088 KB |
Output is correct |
3 |
Correct |
8 ms |
9344 KB |
Output is correct |
4 |
Correct |
8 ms |
9216 KB |
Output is correct |
5 |
Correct |
8 ms |
8704 KB |
Output is correct |
6 |
Correct |
7 ms |
8832 KB |
Output is correct |
7 |
Correct |
8 ms |
8960 KB |
Output is correct |
8 |
Correct |
6 ms |
7424 KB |
Output is correct |
9 |
Correct |
6 ms |
7584 KB |
Output is correct |
10 |
Correct |
6 ms |
8320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
24440 KB |
Output is correct |
2 |
Correct |
24 ms |
23416 KB |
Output is correct |
3 |
Correct |
24 ms |
26752 KB |
Output is correct |
4 |
Correct |
26 ms |
25080 KB |
Output is correct |
5 |
Correct |
23 ms |
20096 KB |
Output is correct |
6 |
Correct |
20 ms |
17792 KB |
Output is correct |
7 |
Correct |
21 ms |
20224 KB |
Output is correct |
8 |
Correct |
9 ms |
7808 KB |
Output is correct |
9 |
Correct |
12 ms |
12032 KB |
Output is correct |
10 |
Correct |
19 ms |
18176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
58496 KB |
Output is correct |
2 |
Correct |
55 ms |
53380 KB |
Output is correct |
3 |
Correct |
68 ms |
65536 KB |
Output is correct |
4 |
Correct |
61 ms |
56576 KB |
Output is correct |
5 |
Correct |
87 ms |
46444 KB |
Output is correct |
6 |
Correct |
50 ms |
48384 KB |
Output is correct |
7 |
Correct |
47 ms |
44800 KB |
Output is correct |
8 |
Correct |
11 ms |
8328 KB |
Output is correct |
9 |
Correct |
11 ms |
8328 KB |
Output is correct |
10 |
Correct |
62 ms |
39424 KB |
Output is correct |
11 |
Correct |
59 ms |
53760 KB |
Output is correct |
12 |
Correct |
16 ms |
13448 KB |
Output is correct |