#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 = 2; 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 = 0; 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 |
1 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 |
600 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
344 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 |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
456 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
0 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 |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2312 KB |
Output is correct |
2 |
Correct |
2 ms |
2232 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 |
22032 KB |
Output is correct |
2 |
Correct |
15 ms |
19852 KB |
Output is correct |
3 |
Correct |
17 ms |
22804 KB |
Output is correct |
4 |
Correct |
16 ms |
21012 KB |
Output is correct |
5 |
Correct |
14 ms |
18252 KB |
Output is correct |
6 |
Correct |
13 ms |
17944 KB |
Output is correct |
7 |
Correct |
15 ms |
16664 KB |
Output is correct |
8 |
Correct |
2 ms |
1748 KB |
Output is correct |
9 |
Correct |
6 ms |
6760 KB |
Output is correct |
10 |
Correct |
12 ms |
17148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
62720 KB |
Output is correct |
2 |
Correct |
49 ms |
64860 KB |
Output is correct |
3 |
Correct |
53 ms |
65704 KB |
Output is correct |
4 |
Correct |
47 ms |
64468 KB |
Output is correct |
5 |
Correct |
44 ms |
65124 KB |
Output is correct |
6 |
Correct |
41 ms |
65636 KB |
Output is correct |
7 |
Correct |
34 ms |
48128 KB |
Output is correct |
8 |
Correct |
7 ms |
4620 KB |
Output is correct |
9 |
Correct |
7 ms |
4572 KB |
Output is correct |
10 |
Correct |
34 ms |
42336 KB |
Output is correct |
11 |
Correct |
47 ms |
63340 KB |
Output is correct |
12 |
Correct |
11 ms |
9688 KB |
Output is correct |