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 ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 300005
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
ll mx = 1;
struct Node{
Node *c[26], *p[19];
int sz = 0, de;
int trav(){
for(int i = 0; i < 26; ++i){
if(!c[i])
continue;
sz += c[i] -> trav();
delete(c[i]);
c[i] = NULL;
}
mx = max(mx, 1LL * de * sz);
return sz;
}
Node* go(int a){
if(c[a])
return c[a];
c[a] = new Node();
c[a] -> de = de + 2;
c[a] -> p[0] = this;
for(int i = 1; ; ++i){
c[a] -> p[i] = c[a] -> p[i - 1] -> p[i - 1];
if(!c[a] -> p[i]) break;
}
return c[a];
}
} *r1 = new Node();
int d1[N];
Node *w1[N];
int a[N];
int lg[N];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string s;
cin>>s;
for(int i = 2; i < N; i <<= 1)
lg[i] = lg[i >> 1] + 1;
r1 -> de = -1;
int n = s.size();
for(int i = 0; i < n; ++i)
a[i] = s[i] - 'a';
int lo = -1, r = -1;
for(int i = 0; i < n; ++i){
if(r < i){
d1[i] = 1;
w1[i] = r1 -> go(a[i]);
} else {
w1[i] = w1[lo - (i - lo)];
d1[i] = d1[lo - (i - lo)];
int w = max(0, d1[i] - (r - i));
d1[i] -= w;
while(w){
w1[i] = w1[i] -> p[lg[w & -w]];
w -= w & -w;
}
}
while(i + d1[i] < n && i - d1[i] >= 0 && a[i - d1[i]] == a[i + d1[i]]){
w1[i] = w1[i] -> go(a[i + d1[i]]);
++d1[i];
}
++w1[i] -> sz;
if(r <= i + d1[i] - 1){
r = i + d1[i] - 1;
lo = i;
}
}
r1 -> trav();
r1 -> de = 0;
lo = -1, r = -1;
for(int i = 0; i < n; ++i){
if(r < i){
d1[i] = 0;
w1[i] = r1;
} else {
w1[i] = w1[lo - (i - lo)];
d1[i] = d1[lo - (i - lo)];
int w = max(0, d1[i] - (r - i));
d1[i] -= w;
while(w){
w1[i] = w1[i] -> p[lg[w & -w]];
w -= w & -w;
}
}
while(i + d1[i] < n && i - d1[i] - 1 >= 0 && a[i - d1[i] - 1] == a[i + d1[i]]){
w1[i] = w1[i] -> go(a[i + d1[i]]);
++d1[i];
}
++w1[i] -> sz;
if(r <= i + d1[i] - 1){
r = i + d1[i] - 1;
lo = i;
}
}
r1 -> trav();
cout<<mx;
}
# | 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... |