Submission #885037

#TimeUsernameProblemLanguageResultExecution timeMemory
885037patrikpavic2Palindromes (APIO14_palindrome)C++17
0 / 100
5 ms1224 KiB
#include <algorithm> #include <vector> #include <cstdio> #include <cstring> #include <iostream> #define PB push_back using namespace std; typedef long long ll; const int N = 3e5 + 500; const int INF = 0x3f3f3f3f; struct node{ node *ch[30], *bk; int len, cnt; node() {} node(int _len) { len = _len; } }; bool cmp(node* X, node* Y){ return X->len > Y->len; } string s; int n; ll mx; vector < node* > v; void precompute(){ node *n1 = new node(-1); node *n0 = new node(0); n0->bk = n1; n1->bk = n1; node* cur = n0; for(int i = 0;i < n;i++){ for(; cur->len + 1 > i || s[i - cur->len - 1] != s[i]; cur = cur->bk); node *rmb = cur->bk; if(!cur->ch[s[i] - 'a']) cur->ch[s[i] - 'a'] = new node(cur->len+2), v.PB(cur->ch[s[i] - 'a']); cur = cur->ch[s[i] - 'a']; cur->cnt++; for(; rmb->len + 1 > i || s[i - rmb->len - 1] != s[i]; rmb = rmb->bk); if(cur->len == 1) cur->bk = n0; else{ if(!rmb->ch[s[i] - 'a']) rmb->ch[s[i] - 'a'] = new node(rmb->len+2), v.PB(rmb->ch[s[i] - 'a']); cur->bk = rmb->ch[s[i] - 'a']; } } } int main(){ cin >> s; n = (int)s.size(); precompute(); sort(v.begin(), v.end(), cmp); for(int i = 0;i < v.size();i++){ mx = max(mx, (ll)v[i]->len * v[i]->cnt); v[i]->bk->cnt += v[i]->cnt; } cout << mx << endl; }

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:62:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 0;i < v.size();i++){
      |                   ~~^~~~~~~~~~
#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...