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 node {
node* nxt[26];
node* failLink; /// pointer la cel mai lung sufix care este palindrom(diferit de tot palindromul)
int len; /// lungimea
int64_t freq; /// la final va fi frecventa palindromului in toate subsecventele
node() {
for (int c = 0; c < 26; ++c) {
nxt[c] = nullptr;
}
failLink = nullptr;
len = 0;
freq = 0;
}
};
void maxSelf(int64_t &x, int64_t y) {
if (x < y) {
x = y;
}
}
struct PalindromicTree {
node* odd;
node* even;
node* last; /// ultimul nod in care am ajuns pana acum
string s;
vector<node*> nodes; /// palindromurile obtinute in ordinea in care apar in sir
PalindromicTree(const string &str) {
s = str;
odd = new node();
nodes.emplace_back(odd);
even = new node();
nodes.emplace_back(even);
odd->len = -1;
odd->failLink = odd;
even->failLink = odd;
last = odd;
}
void extend(int pos) {
while (s[pos - last->len - 1] != s[pos]) {
last = last->failLink;
}
int ch = s[pos] - 'a';
if (last->nxt[ch]) {
last = last->nxt[ch];
last->freq += 1;
return;
}
last->nxt[ch] = new node();
nodes.emplace_back(last->nxt[ch]);
last->nxt[ch]->freq = 1;
last->nxt[ch]->len = last->len + 2;
last->nxt[ch]->failLink = even;
if (last->nxt[ch]->len == 1) {
last = last->nxt[ch];
return;
}
node* suff = last->failLink;
last = last->nxt[ch];
while (s[pos - suff->len - 1] != s[pos]) {
suff = suff->failLink;
}
last->failLink = suff->nxt[ch];
}
int64_t solve() {
reverse(nodes.begin(), nodes.end());
int64_t ans = 0;
for (auto it : nodes) {
it->failLink->freq += it->freq;
maxSelf(ans, it->freq * it->len);
}
return ans;
}
};
void testCase() {
string s;
cin >> s;
int n = s.size();
s = '$' + s;
PalindromicTree t(s);
for (int i = 1; i <= n; ++i) {
t.extend(i);
}
cout << t.solve() << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int tests = 1;
for (int tc = 0; tc < tests; ++tc) {
testCase();
}
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... |