Submission #530494

#TimeUsernameProblemLanguageResultExecution timeMemory
530494Alex_tz307Palindromes (APIO14_palindrome)C++17
100 / 100
61 ms73700 KiB
#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(); last->nxt[ch]->len = last->len + 2; node* suff = last->failLink; last = last->nxt[ch]; last->freq = 1; last->failLink = even; nodes.emplace_back(last); if (last->len == 1) { return; } 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...