Submission #549642

#TimeUsernameProblemLanguageResultExecution timeMemory
549642krit3379Palindromes (APIO14_palindrome)C++17
100 / 100
38 ms39124 KiB
#include<bits/stdc++.h> using namespace std; #define N 300005 struct node{ int nxt[26]; int deg; int len; int suff; long long cnt; }t[N]; int num,suff; long long ans; string s; queue<int> q; void add(int pos){ int cur=suff,idx=s[pos]-'a'; while(true){ if(pos-t[cur].len-1>=0&&s[pos-t[cur].len-1]==s[pos])break; cur=t[cur].suff; } if(t[cur].nxt[idx]){ suff=t[cur].nxt[idx]; t[suff].cnt++; return ; } t[cur].nxt[idx]=++num; t[num].len=t[cur].len+2; t[num].cnt++; suff=num; if(t[num].len==1){ t[num].suff=2; return ; } while(true){ cur=t[cur].suff; if(pos-t[cur].len-1>=0&&s[pos-t[cur].len-1]==s[pos])break; } t[num].suff=t[cur].nxt[idx]; t[t[num].suff].deg++; } void init(){ num=2,suff=2; t[1].len=-1,t[1].suff=1; t[2].len=0,t[2].suff=1; } int main(){ ios_base::sync_with_stdio(false);cin.tie(nullptr); int i,a; cin>>s; init(); for(i=0;i<s.length();i++)add(i); for(i=3;i<=num;i++)if(!t[i].deg)q.push(i); while(!q.empty()){ a=q.front(); q.pop(); if(a<=2)continue; t[t[a].suff].cnt+=t[a].cnt; if(!--t[t[a].suff].deg)q.push(t[a].suff); ans=max(ans,t[a].cnt*t[a].len); } cout<<ans; return 0; }

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:56:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(i=0;i<s.length();i++)add(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...