#include <bits/stdc++.h>
// #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define ss second
#define ff first
void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
cin.tie(0) -> sync_with_stdio(0);
#ifndef ONLINE_JUDGE
#define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
#else
#define er(args ...) 0
#endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 6e5 + 5, p = 9973, lg = 22, inf = ll(1e9) + 5;
// ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;}
struct hhh{
vector<int> pw, hsh;
ll p, mod;
hhh(string s, ll p, ll mod): p(p), mod(mod){
int n = sz(s);
hsh.resize(n), pw.resize(n + 1);
hsh[0] = s[0];
rep(i,1,n){
hsh[i] = (p*hsh[i-1] + s[i])%mod;
}
pw[0] = 1;
rep(i,1,n+1){
pw[i] = p*pw[i-1]%mod;
}
}
int get(int l, int r){
return (hsh[r] - (l? 1ll*hsh[l-1]*pw[r-l+1]%mod :0) + mod)%mod;
}
};
int vl[maxn][2], adj[maxn][26], ptr = 1, hsh[maxn];
map<int, int> id;
map<int, bool> is;
ll ans;
string tmp;
void dfs(int r, int h = 0){
// er(r, tmp);
rep(i,0,26) if(adj[r][i]){
// tmp.pb(char('a' + i));
dfs(adj[r][i], h+1);
// tmp.pop_back();
vl[r][0] += vl[adj[r][i]][0];
vl[r][1] += vl[adj[r][i]][1];
}
ans = max({
ans,
2ll*vl[r][0]*h - vl[r][0],
2ll*vl[r][1]*h
});
}
int main(){ IOS();
string s; cin >> s;
int n = sz(s);
hhh hs(s, p, mod);
reverse(all(s));
hhh hrs(s, p, mod);
reverse(all(s));
auto get = [&](int l, int r){
return hs.get(l, r) == hrs.get(n-1-r, n-1-l);
};
// rep(i,0,n) er(get(i,i));
int tmp = 0, mx = -1;
rep(i,0,n){
int lx = 0, rx = min(i+1, mx-i+2);
// er(i, rx);
while(lx + 1 < rx){
int mid = (lx + rx)>>1;
if(get(i-mid+1, i+mid-1)) lx = mid;
else rx = mid;
}
// er(i, lx, rx, get(i, i));
int cr = lx == 0? 0: id[hs.get(i, i + lx-1)];
if(lx == mx-i+1){
rep(l,rx,min(i+1,n-i)+1){
if(s[i-l+1] == s[i+l-1]){
tmp++;
int c = s[i+l-1]-'a';
if(!adj[cr][c]){
hsh[ptr] = (p*hsh[cr] + s[i+l-1])%mod;
id[hsh[ptr]] = ptr;
adj[cr][c] = ptr++;
}
cr = adj[cr][c];
mx = i+l-1;
} else break;
}
// er(i, mx);
}
vl[cr][0]++;
// rep(l,rx,min(i+1,n-i)+1){
// if(s[i-l+1] == s[i+l-1]){
// tmp++;
// int c = s[i+l-1]-'a';
// if(!adj[cr][c]){
// hsh[ptr] = (p*hsh[cr] + s[i+l-1])%mod;
// id[hsh[ptr]] = ptr;
// adj[cr][c] = ptr++;
// }
// cr = adj[cr][c];
// } else break;
// }
// // er(i, cr);
// vl[cr][0]++;
}
// assert(tmp < 3*n);
rep(i,1,n){
if(s[i] - s[i-1]) continue;
mx = max(mx, i-1);
int lx = 0, rx = min(i+1, mx-i+2);
while(lx + 1 < rx){
int mid = (lx + rx)>>1;
if(get(i-mid, i+mid-1)) lx = mid;
else rx = mid;
}
int cr = lx == 0? 0: id[hs.get(i, i + lx-1)];
if(lx == mx - i + 1){
rep(l,rx,min(i,n-i)+1){
if(s[i+l-1] == s[i-l]){
int c = s[i+l-1]-'a';
if(!adj[cr][c]){
hsh[ptr] = (p*hsh[cr] + s[i+l-1])%mod;
id[hsh[ptr]] = ptr;
adj[cr][c] = ptr++;
}
cr = adj[cr][c];
mx = i + l - 1;
} else break;
}
}
er(i, mx);
vl[cr][1]++;
}
dfs(0);
cout << ans << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
16 ms |
772 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
14 ms |
852 KB |
Output is correct |
6 |
Correct |
15 ms |
852 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
4 ms |
560 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Incorrect |
5 ms |
468 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
2380 KB |
Output is correct |
2 |
Correct |
8 ms |
2308 KB |
Output is correct |
3 |
Correct |
168 ms |
5768 KB |
Output is correct |
4 |
Correct |
142 ms |
5736 KB |
Output is correct |
5 |
Correct |
6 ms |
2260 KB |
Output is correct |
6 |
Correct |
30 ms |
2772 KB |
Output is correct |
7 |
Correct |
12 ms |
2340 KB |
Output is correct |
8 |
Correct |
6 ms |
596 KB |
Output is correct |
9 |
Correct |
7 ms |
724 KB |
Output is correct |
10 |
Incorrect |
46 ms |
1868 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
112 ms |
21172 KB |
Output is correct |
2 |
Correct |
103 ms |
19772 KB |
Output is correct |
3 |
Execution timed out |
1089 ms |
40096 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
455 ms |
62760 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |