#include <bits/stdc++.h>
using namespace std;
template<const int A>
class eertree {
private:
string s;
int n, id, cr, I;
vector<int> P, L, C;
vector<array<int, A>> T;
int par(int v) {
while (I - L[v] - 2 < 0 || s[I - L[v] - 2] != s[I - 1]) {
v = P[v];
}
return v;
}
void add() {
int ch = s[I++] - 'a';
cr = par(cr);
if (!T[cr][ch]) {
L[id] = L[cr] + 2;
P[id] = T[par(P[cr])][ch];
T[cr][ch] = id++;
}
cr = T[cr][ch];
C[cr]++;
}
public:
eertree(const string& _s) {
s = _s;
n = s.length();
id = 2;
cr = I = 0;
P.assign(n + 2, 0);
L.assign(n + 2, 0);
C.assign(n + 2, 0);
T.assign(n + 2, {});
L[1] = -1;
P[0] = 1;
for (int i = 0; i < n; i++) {
add();
}
}
long long solve() {
for (int i = n + 1; i > 1; i--) {
C[P[i]] += C[i];
}
long long res = 0;
for (int i = 2; i < n + 2; i++) {
res = max(res, L[i] * 1LL * C[i]);
}
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
string s;
cin >> s;
cout << eertree<26>(s).solve() << '\n';
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
312 KB |
Output is correct |
| 5 |
Correct |
1 ms |
308 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
332 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
316 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
312 KB |
Output is correct |
| 21 |
Correct |
1 ms |
204 KB |
Output is correct |
| 22 |
Correct |
1 ms |
308 KB |
Output is correct |
| 23 |
Correct |
1 ms |
204 KB |
Output is correct |
| 24 |
Correct |
1 ms |
312 KB |
Output is correct |
| 25 |
Correct |
1 ms |
204 KB |
Output is correct |
| 26 |
Correct |
1 ms |
204 KB |
Output is correct |
| 27 |
Correct |
1 ms |
204 KB |
Output is correct |
| 28 |
Correct |
1 ms |
204 KB |
Output is correct |
| 29 |
Correct |
1 ms |
204 KB |
Output is correct |
| 30 |
Correct |
1 ms |
204 KB |
Output is correct |
| 31 |
Correct |
1 ms |
204 KB |
Output is correct |
| 32 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
312 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1472 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1484 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1484 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1484 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1484 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1484 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1484 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1484 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1484 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1484 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
12004 KB |
Output is correct |
| 2 |
Correct |
11 ms |
11904 KB |
Output is correct |
| 3 |
Correct |
9 ms |
11952 KB |
Output is correct |
| 4 |
Correct |
10 ms |
12000 KB |
Output is correct |
| 5 |
Correct |
10 ms |
11976 KB |
Output is correct |
| 6 |
Correct |
10 ms |
11984 KB |
Output is correct |
| 7 |
Correct |
10 ms |
11996 KB |
Output is correct |
| 8 |
Correct |
9 ms |
11980 KB |
Output is correct |
| 9 |
Correct |
9 ms |
11980 KB |
Output is correct |
| 10 |
Correct |
9 ms |
12000 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
28 ms |
35392 KB |
Output is correct |
| 2 |
Correct |
28 ms |
35288 KB |
Output is correct |
| 3 |
Correct |
27 ms |
35284 KB |
Output is correct |
| 4 |
Correct |
27 ms |
35384 KB |
Output is correct |
| 5 |
Correct |
26 ms |
35364 KB |
Output is correct |
| 6 |
Correct |
26 ms |
35380 KB |
Output is correct |
| 7 |
Correct |
26 ms |
35384 KB |
Output is correct |
| 8 |
Correct |
22 ms |
35284 KB |
Output is correct |
| 9 |
Correct |
24 ms |
35400 KB |
Output is correct |
| 10 |
Correct |
26 ms |
35348 KB |
Output is correct |
| 11 |
Correct |
27 ms |
35312 KB |
Output is correct |
| 12 |
Correct |
23 ms |
35284 KB |
Output is correct |
