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;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
const int A = 27;
struct trie_node {
int depth;
trie_node* parent;
trie_node* e[A];
int cnt;
trie_node() {
depth = 0;
parent = nullptr;
for (int i = 0; i < A; ++i) e[i] = nullptr;
cnt = 0;
}
};
void add_edge(trie_node *v, char c) {
assert(v != nullptr);
int x = c - 'a';
if (v->e[x] != nullptr) return;
trie_node *u = v->e[x] = new trie_node;
u->depth = v->depth + 1;
u->parent = v;
}
ll dfs(trie_node *v) {
ll res = 0;
for (int i = 0; i < A; ++i) {
if (v->e[i] != nullptr) {
res = max(res, dfs(v->e[i]));
v->cnt += v->e[i]->cnt;
delete v->e[i];
}
}
return max(res, ll(v->cnt) * ll(v->depth - 1));
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
string s;
cin >> s;
int n = ssize(s);
char filler = 'z' + 1;
string tmp;
tmp.push_back(filler);
for (char x : s) {
tmp.push_back(x);
tmp.push_back(filler);
}
s = tmp;
n = ssize(s);
vector<int> r(n);
int f = 0;
r[0] = 1;
vector<trie_node*> Node(n+1);
Node[0] = new trie_node;
add_edge(Node[0], s[0]);
Node[1] = Node[0]->e[s[0]-'a'];
for (int i = 1; i < n; ++i) {
int parent = 0;
r[i] = 0;
if (f + r[f] - 1 >= i) {
int sym = 2*f - i;
if (sym >= 0) {
r[i] = max(r[i], min(r[sym], sym - (f - r[f])));
parent = sym+1;
}
}
int v = i+1;
Node[v] = Node[parent];
while (Node[v]->depth != r[i]) Node[v] = Node[v]->parent;
while (i - r[i] >= 0 && i + r[i] < n && s[i-r[i]] == s[i+r[i]]) {
add_edge(Node[v], s[i+r[i]]);
Node[v] = Node[v]->e[s[i+r[i]]-'a'];
r[i]++;
}
Node[v]->cnt++;
if (i + r[i] >= f + r[f]) f = i;
}
ll res = dfs(Node[0]);
delete Node[0];
cout << res << '\n';
return 0;
}
# | 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... |