#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define pb push_back
const int N = 1e5+11;
const ll baza = 37, MOD = 1e9+7;
string s;
int n;
ll hf[N], hb[N];
pair <ll, ll> sweep[N];
ll p[26][N];
ll suma;
ll pot[N];
ll mns[N];
ll add (ll a, ll b) {
ll ret = a+b;
if (ret > MOD) ret -= MOD;
if (ret < 0) ret += MOD;
return ret;
}
ll mult (ll a, ll b) {
ll ret = a*b;
ret %= MOD;
if (ret < 0) ret += MOD;
return ret;
}
void hashiranje() {
hf[0] = (s[0] - 'a' + 1);
ll mno = baza;
for (int i=1;i<n;i++) {
hf[i] = mult (s[i] - 'a' + 1, mno);
mno = mult(baza, mno);
hf[i] = add (hf[i], hf[i-1]);
}
/////////////////////////////////////////////////
hb[n-1] = (s[n-1] - 'a' + 1);
mno = baza;
for (int i=n-2;i>=0;i--) {
hb[i] = mult(s[i] - 'a' + 1, mno);
mno = mult(baza, mno);
hb[i] = add (hb[i], hb[i+1]);
}
}
bool jesu (int x1, int y1, int x2, int y2) {
ll prvi = hf[y1];
if (x1 > 0) prvi = add(prvi, -hf[x1-1]);
ll drugi = hb[x2];
if (y2 < n-1) drugi = add(drugi, -hb[y2+1]);
int mno1 = y1;
int mno2 = n-1-x2;
if (mno1 > mno2) drugi = mult(drugi, pot[mno1-mno2]);
else prvi = mult(prvi, pot[mno2-mno1]);
if (prvi == drugi) return 1;
else return 0;
}
int isti (int x, int y) {
if (x < 0 || y > n-1) return 0;
if (s[x] != s[y]) return 0;
int lo = 0;
int hi = min(x, n-1-y);
while (lo < hi) {
int mid = (lo+hi)/2+1;
if (jesu(x-mid, x, y, y+mid)) lo = mid;
else hi = mid-1;
}
return lo+1;
}
bool palin (int x, int y) {
return jesu(x, y, x, y);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> s;
n = s.size();
hashiranje();
pot[0] = 1;
for (int i=1;i<n;i++) pot[i] = mult(pot[i-1], baza);
for (int i=0;i<n;i++) {
int lo = 0;
int hi = min(i, n-1-i);
while (lo < hi) {
int mid = (lo+hi)/2+1;
if (palin(i-mid, i+mid)) lo = mid;
else hi = mid-1;
}
int r = lo;
sweep[i-r].ff += 1;
sweep[i].ff += -1;
sweep[i].ss += -r;
if (r > 0) {
sweep[i+1].ff -= 1;
sweep[i+1].ss += r+1;
if (i+r+1 < n) {
sweep[i+r+1].ff += 1;
sweep[i+r+1].ss += -1;
}
}
suma += r+1;
if (i-r-1 < 0 || i+r+1 > n-1) continue;
int sada = isti(i-r-2, i+r+2);
p[s[i+r+1] - 'a'][i-r-1] += sada+1;
p[s[i-r-1] - 'a'][i+r+1] += sada+1;
}
/////////////////////////////////////////////////////////////
for (int i=0;i<n-1;i++) {
if (s[i] != s[i+1]) {
int sada = isti(i-1, i+2);
p[s[i+1]-'a'][i] += sada+1;
p[s[i]-'a'][i+1] += sada+1;
continue;
}
int lo = 0;
int hi = min(i, n-1-i-1);
while (lo < hi) {
int mid = (lo+hi)/2+1;
if (palin(i-mid, i+1+mid)) lo = mid;
else hi = mid-1;
}
int r = lo;
sweep[i-r].ff += 1;
sweep[i+1].ff -= 1;
if (r > 0) {
sweep[i+2].ff -= 1;
if (i+r+2 < n) sweep[i+r+2].ff += 1;
}
suma += r+1;
if (i-r-1 < 0 || i+r+2 > n-1) continue;
int sada = isti(i-r-2, i+r+3);
p[s[i+r+2] - 'a'][i-r-1] += sada+1;
p[s[i-r-1] - 'a'][i+r+2] += sada+1;
}
/////////////////////////////////////////////////////////////
ll dodaj = 0;
for (int i=0;i<n;i++) {
dodaj += sweep[i].ff;
mns[i] += dodaj;
if (i > 0) mns[i] += mns[i-1];
mns[i] += sweep[i].ss;
// cout << mns[i] << " ";
}
ll poc = suma;
for (int i=0;i<n;i++) {
for (int j=0;j<26;j++) {
if (j == s[i]-'a') continue;
suma = max(suma, poc + p[j][i] - mns[i]);
}
}
cout << suma;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
768 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
7032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
