This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct palin_tree {
struct node {
int len, suffix, serial_link = 0, diff = 0, occ = 0;
vector<int> edges;
map<int, int> nxt; // use this if n <= 1e6 and memory <= 256MB
node(int _len = 0, int _suffix = 0) : len(_len), suffix(_suffix) {}
};
vector<node> tree;
vector<char> past;
int turtle;
palin_tree(int expected_size = int(1e6)) : tree(2, node()), past(1, -1) {
tree.reserve(expected_size), past.reserve(expected_size);
tree[0].suffix = 1, tree[1].len = -1;
turtle = 0;
tree[1].edges.push_back(0);
}
int go_back(int u) {
while (past[(int)past.size() - tree[u].len - 2] != past.back())
u = tree[u].suffix;
return u;
}
void append(int c) {
past.push_back(c);
turtle = go_back(turtle);
if (!tree[turtle].nxt[c]) {
node tmp; tmp.len = tree[turtle].len + 2;
tmp.suffix = tree[go_back(tree[turtle].suffix)].nxt[c];
tmp.diff = tmp.len - tree[tmp.suffix].len;
tmp.serial_link = (tmp.diff != tree[tmp.suffix].diff ?
tmp.suffix : tree[tmp.suffix].serial_link);
tmp.occ = 1;
tree[turtle].nxt[c] = (int)tree.size();
tree[tmp.suffix].edges.push_back((int)tree.size());
tree.push_back(tmp);
} else tree[tree[turtle].nxt[c]].occ++;
turtle = tree[turtle].nxt[c];
}
long long solve(int u = 1) {
long long res = 0;
for (int v : tree[u].edges) {
res = max(res, solve(v));
tree[u].occ += tree[v].occ;
}
return max(res, 1LL * tree[u].occ * tree[u].len);
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
string s; s.reserve(int(3e5)); cin >> s;
palin_tree ptree(s.size());
for (auto c : s) ptree.append(c - 'a');
cout << ptree.solve() << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |