# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
31178 | tatatan | Palindromes (APIO14_palindrome) | C++11 | 19 ms | 37912 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>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;
const int N=3e5+5;
int suff[N],len[N],lz[N],nxt[N][26],cur,tt=3;
LL ans;
string s;
stack<int> st;
void add(int x) {
while(s[x-len[cur]-1]!=s[x])
cur=suff[cur];
int y=s[x]-'a';
if(nxt[cur][y]) {
cur=nxt[cur][y];
++lz[cur];
return;
}
int nw=tt++;
st.push(nw);
++lz[nw];
len[nw]=len[cur]+2;
if(len[nw]==1) {
suff[nw]=2;
nxt[cur][y]=nw;
cur=nw;
return;
}
int tmp2=cur;
cur=suff[cur];
while(s[x-len[cur]-1]!=s[x])
cur=suff[cur];
suff[nw]=nxt[cur][y];
cur=nw;
nxt[tmp2][y]=cur;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>s;
len[1]=-1; suff[1]=1;
len[2]=0; suff[2]=1;
cur=1;
for(int i=0;i<s.size();++i)
add(i);
while(!st.empty()) {
int x=st.top();
st.pop();
ans=max(ans,1LL*len[x]*lz[x]);
lz[suff[x]]+=lz[x];
}
cout<<ans<<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... |