# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
250230 | errorgorn | Palindromes (APIO14_palindrome) | C++14 | 32 ms | 35080 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |