Submission #250230

#TimeUsernameProblemLanguageResultExecution timeMemory
250230errorgornPalindromes (APIO14_palindrome)C++14
100 / 100
32 ms35080 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ii pair<ll,ll> #define iii pair<ll,ii> #define endl '\n' int edges[300005][26]; int backedge[300005]; int len[300005]; int PREV=0; int INDEX=1; int cnt[300005]; string s; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>s; memset(edges,-1,sizeof(edges)); backedge[0]=0,backedge[1]=0; len[0]=-1,len[1]=0; for (int x=0;x<s.size();x++){ while (s[x-len[PREV]-1]!=s[x]) PREV=backedge[PREV]; if (edges[PREV][s[x]-'a']==-1) edges[PREV][s[x]-'a']=++INDEX; int curr=edges[PREV][s[x]-'a']; len[curr]=len[PREV]+2; if (len[curr]==1){ backedge[curr]=1; } else{ int b=backedge[PREV]; while (s[x-len[b]-1]!=s[x]) b=backedge[b]; backedge[curr]=edges[b][s[x]-'a']; } PREV=curr; cnt[curr]++; //cout<<curr<<endl; } ll best=0; for (int x=INDEX;x>1;x--){ best=max(best,(ll)cnt[x]*len[x]); cnt[backedge[x]]+=cnt[x]; } cout<<best<<endl; }

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int x=0;x<s.size();x++){
               ~^~~~~~~~~
#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...