# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
549642 | krit3379 | Palindromes (APIO14_palindrome) | C++17 | 38 ms | 39124 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 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)
# | 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... |