#include <bits/stdc++.h>
using namespace std;
void main_program();
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
main_program();
}
template <class T, class Adj>
struct PalindromeTree {
vector<int> len, link, occur;
vector<Adj> nxt;
PalindromeTree(){
len = vector<int>{0, -1};
link = vector<int>{1, 0};
occur = vector<int>{1, 0};
nxt = vector<Adj>(2);
}
PalindromeTree(const vector<T> &str): PalindromeTree() {
add(str);
}
int new_node(int length, int sfx_link){
len.push_back(length);
link.push_back(sfx_link);
nxt.emplace_back();
occur.push_back(0);
return (int)len.size() - 1;
}
vector<T> s;
int last = 0;
void add(T c){
s.push_back(c);
int crr = last;
while (s[(int)s.size() - len[crr] - 2] != c) crr = link[crr];
if (!nxt[crr][c]){
int u = link[crr];
while (s[(int)s.size() - len[u] - 2] != c) u = link[u];
int v = new_node(len[crr] + 2, nxt[u][c]);
nxt[crr][c] = v;
}
last = nxt[crr][c];
occur[last]++;
}
void add(const vector<T> &str){
for (auto c: str) add(c);
}
vector<int> cnt;
vector<vector<int>> inv_link;
void dfs(int x){
for (auto child: inv_link[x]){
dfs(child);
cnt[x] += cnt[child];
}
}
int size() const { return len.size(); }
void init_count(){
cnt = occur;
inv_link.assign(size(), {});
for (int i = 1; i < size(); i++) inv_link[link[i]].push_back(i);
dfs(0);
}
};
void main_program(){
string s; cin >> s;
vector<int> v(s.size());
for (int i = 0; i < (int)s.size(); i++){
v[i] = s[i] - 'a';
}
PalindromeTree<int, array<int, 26>> tree(v);
tree.init_count();
long long res = 0;
for (int i = 2; i < (int)tree.size(); i++){
res = max(res, 1LL * tree.len[i] * tree.cnt[i]);
}
cout << res << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
0 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
0 ms |
604 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2672 KB |
Output is correct |
2 |
Correct |
2 ms |
2236 KB |
Output is correct |
3 |
Incorrect |
1 ms |
1476 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
21524 KB |
Output is correct |
2 |
Correct |
15 ms |
20512 KB |
Output is correct |
3 |
Correct |
16 ms |
22032 KB |
Output is correct |
4 |
Correct |
16 ms |
22292 KB |
Output is correct |
5 |
Correct |
15 ms |
18452 KB |
Output is correct |
6 |
Correct |
12 ms |
17944 KB |
Output is correct |
7 |
Correct |
13 ms |
16920 KB |
Output is correct |
8 |
Correct |
2 ms |
1752 KB |
Output is correct |
9 |
Correct |
5 ms |
6260 KB |
Output is correct |
10 |
Correct |
14 ms |
17172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
63084 KB |
Output is correct |
2 |
Correct |
48 ms |
64096 KB |
Output is correct |
3 |
Correct |
48 ms |
65796 KB |
Output is correct |
4 |
Correct |
44 ms |
64924 KB |
Output is correct |
5 |
Correct |
44 ms |
63848 KB |
Output is correct |
6 |
Correct |
44 ms |
65624 KB |
Output is correct |
7 |
Correct |
35 ms |
46872 KB |
Output is correct |
8 |
Correct |
6 ms |
4316 KB |
Output is correct |
9 |
Correct |
7 ms |
4316 KB |
Output is correct |
10 |
Correct |
33 ms |
42848 KB |
Output is correct |
11 |
Correct |
44 ms |
64100 KB |
Output is correct |
12 |
Correct |
10 ms |
8920 KB |
Output is correct |