Submission #530838

#TimeUsernameProblemLanguageResultExecution timeMemory
530838new_accPalindromes (APIO14_palindrome)C++14
100 / 100
159 ms92364 KiB
#include<bits/stdc++.h> #define fi first #define se second #define pitem item* using namespace std; typedef long long ll; typedef vector<ll> vi; typedef vector<ll> vl; struct item{ pitem fail; int l,il; pitem g[27]; }; const int N=3e5+10; string s; item *k1,*k2; vector<pitem> k[N]; pitem add(int ind,pitem curr){ while(curr!=nullptr){ if(ind+1>=(curr->l)+2 and s[ind-(curr->l)-1]==s[ind]) break; curr=curr->fail; } if(curr->g[int(s[ind])-96]!=nullptr) { curr->g[int(s[ind])-96]->il++; return curr->g[int(s[ind])-96]; } curr->g[int(s[ind])-96]=new item; curr->g[int(s[ind])-96]->il=1; curr->g[int(s[ind]-96)]->l=curr->l+2; for(int i=1;i<=26;i++) curr->g[int(s[ind])-96]->g[i]=nullptr; pitem pom=curr->g[int(s[ind])-96]; curr=curr->fail; while(curr!=nullptr){ if(ind+1>=(curr->l)+2 and s[ind-(curr->l)-1]==s[ind]) break; curr=curr->fail; } if(curr==nullptr) pom->fail=k2; else pom->fail=curr->g[int(s[ind])-96]; return pom; } void rek(pitem curr){ if(!curr) return; k[curr->l].push_back(curr); for(int i=1;i<=26;i++) rek(curr->g[i]); } void solve(){ cin>>s; k1=new item; k2=new item; k2->fail=k1,k1->fail=nullptr; k1->l=-1,k2->l=0,k1->il=0,k2->il=0; for(int i=1;i<=26;i++) k1->g[i]=nullptr,k2->g[i]=nullptr; pitem curr=k2; for(int i=0;i<s.size();i++) curr=add(i,curr); rek(k1),rek(k2); ll res=0; for(int i=s.size();i>=1;i--){ for(auto u:k[i]){ res=max(res,(ll)(u->il)*(ll)(u->l)); u->fail->il+=u->il; } } cout<<res<<"\n"; } int main(){ ios_base::sync_with_stdio(0),cin.tie(0); solve(); }

Compilation message (stderr)

palindrome.cpp: In function 'void solve()':
palindrome.cpp:54:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i=0;i<s.size();i++) curr=add(i,curr);
      |              ~^~~~~~~~~
#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...