# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
503111 | _tien_ | Palindromes (APIO14_palindrome) | C++14 | 1093 ms | 3568 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 maxn 300005
struct node{
int startt,endd;
int length;
int insertEdg[26];
int suffixEdg;
};
node root1,root2;
node tree[maxn];
int currNode,ans=1;
int dem[maxn];
string s;
int ptr;
void insertt(int idx){
int tmp=currNode;
while(true){
int currLength=tree[tmp].length;
if(idx-currLength>=1 && s[idx] == s[idx-currLength-1])
break;
tmp=tree[tmp].suffixEdg;
}
int x=tmp;
while(true){
int currLength=tree[tmp].length;
if(idx-currLength>=1 && s[idx] == s[idx-currLength-1])
dem[tree[x].insertEdg[s[idx]-'a']]++;
if(x==1||x==2)break;
x=tree[x].suffixEdg;
}
if(tree[tmp].insertEdg[s[idx]-'a']!=0){
currNode=tree[tmp].insertEdg[s[idx]-'a'];
return ;
}
ptr++;dem[ptr]++;
tree[tmp].insertEdg[s[idx]-'a']=ptr;
tree[ptr].length=tree[tmp].length+2;
tree[ptr].endd=idx;
tree[ptr].startt=idx-tree[ptr].length+1;
tmp=tree[tmp].suffixEdg;
currNode=ptr;
if(tree[currNode].length==1){
tree[currNode].suffixEdg=2;
return;
}
while(true){
int currLength=tree[tmp].length;
if(idx-currLength>=1&&s[idx]==s[idx-currLength-1])
break;
tmp=tree[tmp].suffixEdg;
}
tree[currNode].suffixEdg=tree[tmp].insertEdg[s[idx]-'a'];
}
int main(){
ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
root1.length=-1;
root1.suffixEdg=1;
root2.length=0;
root2.suffixEdg=1;
tree[1]=root1;
tree[2]=root2;
ptr=2;
currNode=1;
cin>>s;
for(int i=0;i<s.length();i++)
insertt(i);
for(int i=3;i<=ptr;i++)
ans=max(ans,tree[i].length*dem[i]);
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... |