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;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int MN = 300300;
const int MA = 26;
const int LOG = 20;
vi tr[MA];
vi anc[MA];
vl so;
void adn() {
for(int i=0;i<MA;i++) {
tr[i].push_back(-1);
anc[i].push_back(-1);
}
so.push_back(0);
}
int mov(int u, int go) {
if(tr[go][u] == -1) {
int nx = tr[go].size();
adn();
tr[go][u] = nx;
anc[0][nx] = u;
for(int i=1;i<MA;i++) {
anc[i][nx] = anc[i-1][anc[i-1][nx]];
}
return nx;
} else {
return tr[go][u];
}
}
int ganc(int u, int an) {
for(int i=MA-1;i>=0;i--) {
if(an&(1<<i)) {
u = anc[i][u];
}
}
return u;
}
vi ra,rb,wa,wb;
void manc(const string& s) {
ra.assign(s.size(),-1);
rb.assign(s.size(),-1);
wa.assign(s.size(),-1);
wb.assign(s.size(),-1);
int n = s.size();
for(int i=0,l=0,r=-1;i<n;i++) {
int st;
int k;
if(i > r) {
k = 1;
st = mov(0,s[i]-'a');
} else {
k = min(ra[l+r-i],r-i+1);
st = ganc(wa[l+r-i],ra[l+r-i]-k);
}
while(i-k >= 0 && i+k < n && s[i-k] == s[i+k]) {
st = mov(st,s[i+k]-'a');
k++;
}
ra[i] = k;k--;
wa[i] = st;
if(i+k > r) {
l = i-k;
r = i+k;
}
so[st]++;
}
for(int i=0,l=0,r=-1;i<n;i++) {
int st;
int k;
if(i > r) {
k = 0;
st = 1;
} else {
k = min(rb[r+l-i-1],r-i+1);
st = ganc(wb[r+l-i-1],rb[r+l-i-1]-k);
}
while(i-k-1 >= 0 && i+k < n && s[i-k-1] == s[i+k]) {
st = mov(st,s[i+k]-'a');
k++;
}
rb[i] = k;k--;
wb[i] = st;
if(i+k > r) {
l = i-k;
r = i+k;
}
so[st]++;
}
}
void dfa(int u) {
for(int i=0;i<MA;i++) {
int v = tr[i][u];
if(v == -1) {continue;}
dfa(v);
so[u] += so[v];
}
}
ll dfb(int u, ll len) {
ll res = 0;
for(int i=0;i<MA;i++) {
int v = tr[i][u];
if(v == -1) {continue;}
res = max(res,dfb(v,len+2));
}
res = max(res,len*so[u]);
return res;
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);
for(int i=0;i<MA;i++) {
tr[i].push_back(-1);
tr[i].push_back(-1);
anc[i].push_back(0);
anc[i].push_back(1);
}
so.push_back(0);
so.push_back(0);
string s;
cin >> s;
manc(s);
dfa(0);dfa(1);
ll res = max(dfb(0,-1),dfb(1,0));
cout << res << '\n';
}
# | 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... |