#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 3;
const int mod[] = {1000000007,998244353};
int pow26[2][maxn],hprefix[2][18][maxn],hsuffix[2][18][maxn];
ll addi[26][maxn],odd[maxn],even[maxn],prefix[maxn];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s;
cin >> s;
int n = s.size();
// Precompute 26^k
pow26[0][0] = pow26[1][0] = 1;
for(int i=0;i<n;i++){
pow26[0][i+1] = (26ll*pow26[0][i])%mod[0];
pow26[1][i+1] = (26ll*pow26[1][i])%mod[1];
}
// Precompute Hashing and Sparse Table
for(int i=0;i<n;i++){
hprefix[0][0][i] = hprefix[1][0][i] = hsuffix[0][0][i] = hsuffix[1][0][i] = s[i]-'a';
}
for(int i=1;i<18;i++){
for(int j=0;j+(1<<i)<=n;j++){
hprefix[0][i][j] = (hprefix[0][i-1][j]+1ll*pow26[0][1<<(i-1)]*hprefix[0][i-1][j+(1<<(i-1))])%mod[0];
hprefix[1][i][j] = (hprefix[1][i-1][j]+1ll*pow26[1][1<<(i-1)]*hprefix[1][i-1][j+(1<<(i-1))])%mod[1];
}
for(int j=n-1;j-(1<<i)>=-1;j--){
hsuffix[0][i][j] = (hsuffix[0][i-1][j]+1ll*pow26[0][1<<(i-1)]*hsuffix[0][i-1][j-(1<<(i-1))])%mod[0];
hsuffix[1][i][j] = (hsuffix[1][i-1][j]+1ll*pow26[1][1<<(i-1)]*hsuffix[1][i-1][j-(1<<(i-1))])%mod[1];
}
}
for(int i=0;i<n-1;i++){
if(i > 0){
int z = 0;
for(int j=17;j>=0;j--){
if(i-1-z-(1<<j) >= -1 && i+1+z+(1<<j) <= n && hsuffix[0][j][i-1-z] == hprefix[0][j][i+1+z] && hsuffix[1][j][i-1-z] == hprefix[1][j][i+1+z]){
odd[i] += (1<<j);
z += (1<<j);
}
}
prefix[i-z+1]--;
prefix[i+1]++;
prefix[i+1]++;
prefix[i+z+1]--;
// cout << i-z+1 << ' ' << i+1 << ' ' << i+z+1 << '\n';
z++;
if(i-1-z >= -1 && i+1+z <= n){
addi[s[i+z]-'a'][i-z]++;
addi[s[i-z]-'a'][i+z]++;
int l = i-1-z, r = i+1+z, v = 0;
for(int j=17;j>=0;j--){
if(l-v-(1<<j) >= -1 && r+v+(1<<j) <= n && hsuffix[0][j][l-v] == hprefix[0][j][r+v] && hsuffix[1][j][l-v] == hprefix[1][j][r+v]){
addi[s[i+z]-'a'][i-z] += (1<<j);
addi[s[i-z]-'a'][i+z] += (1<<j);
v += (1<<j);
}
}
}
}
int z = 0;
for(int j=17;j>=0;j--){
if(i-z-(1<<j) >= -1 && i+1+z+(1<<j) <= n && hsuffix[0][j][i-z] == hprefix[0][j][i+1+z] && hsuffix[1][j][i-z] == hprefix[1][j][i+1+z]){
even[i] += (1<<j);
z += (1<<j);
}
}
prefix[i-z+1]--;
prefix[i+1]++;
prefix[i+2]++;
prefix[i+z+2]--;
// cout << i << ' ' << z << " -> " << i-z+1 << ' ' << i+1 << ' ' << i+2 << ' ' << i+z+2 << '\n';
z++;
if(i-z >= -1 && i+1+z <= n){
addi[s[i+z]-'a'][i-z+1]++;
addi[s[i-z+1]-'a'][i+z]++;
int l = i-z, r = i+1+z, v = 0;
for(int j=17;j>=0;j--){
if(l-v-(1<<j) >= -1 && r+v+(1<<j) <= n && hsuffix[0][j][l-v] == hprefix[0][j][r+v] && hsuffix[1][j][l-v] == hprefix[1][j][r+v]){
addi[s[i+z]-'a'][i-z+1] += (1<<j);
addi[s[i-z+1]-'a'][i+z] += (1<<j);
v += (1<<j);
}
}
}
}
for(int i=1;i<=n;i++){
prefix[i] += prefix[i-1];
}
for(int i=1;i<=n;i++){
prefix[i] += prefix[i-1];
}
ll tot = 0;
for(int i=0;i<=n;i++){
tot += odd[i]+even[i];
}
for(int i=0;i<=n;i++){
prefix[i] += tot;
}
ll res = 0;
for(int i=0;i<n;i++){
res += odd[i] + even[i];
}
for(int i=0;i<n;i++){
ll mx = 0;
for(int j=0;j<26;j++){
// cout << addi[j][i] << " ";
mx = max(mx,addi[j][i]);
}
// cout << "\n";
res = max(res,mx+prefix[i]+odd[i]);
}
cout << res + n << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
468 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1684 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1748 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1748 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
29860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
