#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
using namespace std;
typedef long long ll;
typedef string str;
typedef pair<ll, ll> pll;
// lines are numbered from 0 to n
const ll N = 1e5 + 10;
const ll H = 727;
const ll MOD = 1e9 + 7;
str s;
ll tav_H[N], pr[N], pl[N], sum_lr[N], sum_rl[N], ans_lr[N], ans_rl[N], p_r[N], p_l[N], p_r2[N], p_l2[N];
ll n;
bool isval(int L, int R, int x){
int LL = L - x;
int RR = R + x;
if (LL < 0 || RR > n) return 0;
//cout << LL << ' ' << L << ' ' << R << ' ' << RR << '\n';
ll RH = pr[L] - (pr[LL] * tav_H[L - LL]) % MOD;
ll LH = pl[R] - (pl[RR] * tav_H[L - LL]) % MOD;
RH %= MOD;
RH += MOD;
RH %= MOD;
LH %= MOD;
LH += MOD;
LH %= MOD;
return (RH == LH);
}
int BS(int L, int R){
//if (s[L] != s[R + 1]) return 0;
int l = 0, r = L + 2;
while (r - l > 1){
int mid = (l + r) >> 1;
if (isval(L, R, mid)) l = mid;
else r = mid;
}
return l;
}
vector<pll> L_P[N], R_P[N];
int main(){
cin >> s;
tav_H[0] = 1;
n = s.size();
for (int i = 1; i < N; i++) tav_H[i] = tav_H[i - 1] * H % MOD;
for (int i = 1; i <= n; i++){
pr[i] = pr[i - 1] * H + s[i - 1] + 3;
pr[i] %= MOD;
}
ll ans = 0;
for (int i = n - 1; i >= 0; i--){
pl[i] = pl[i + 1] * H + s[i] + 3;
pl[i] %= MOD;
}
for (int i = 0; i <= n; i++){
if (i != n){
// cout << i << ' ' << i + 1 << ' ';
int x = BS(i, i + 1);
// cout << x << '\n';
ans += BS(i, i + 1) + 1;
L_P[i - BS(i, i + 1)].pb({i, i + 1});
R_P[i + 1 + BS(i, i + 1)].pb({i, i + 1});
//cout << i << ' ' << i + 1 << ' ' << i - x << ' ' << i << '\n';
p_r[i - x] --;
p_r[i] ++;
p_r2[i] += x;
p_l[i] ++;
p_l2[i] += x;
p_l[i + x] --;
}
if (i != 0){
int x = BS(i, i);
ans += BS(i, i);
L_P[i - BS(i, i)].pb({i, i});
R_P[i + BS(i, i)].pb({i, i});
// cout << i << ' ' << i << ' ' << i - x << ' ' << i << '\n';
p_r[i - x] --;
p_r2[i] += x;
p_r[i] ++;
p_l[i - 1] ++;
p_l2[i - 1] += x;
p_l[i + x - 1] --;
}
}
ll res = ans;
// cout << BS(0, 3) << ' ' << BS(1, 3) << '\n';
//cout << ans << '\n';
//for (int i = 0; i < n; i++) cout << p_r[i] << '\n';
for (int i = 1; i <= n; i++) p_r[i] += p_r[i - 1];
//cout << '\n';
p_r[0] += p_r2[0];
for (int i = 1; i <= n; i++) p_r[i] += p_r[i - 1] + p_r2[i];
//cout << '\n';
for (int i = n; i >= 0; i--) p_l[i] += p_l[i + 1];
p_l[n] += p_l2[n];
for (int i = n; i >= 0; i--) p_l[i] += p_l[i + 1] + p_l2[i];
// for (int i = 0; i < n; i++) cout << p_r[i] << ' ';
//cout << '\n';
//cout << ans << ' ';
for (int i = 0; i < s.size(); i++){
for (int j = 0; j < 26; j++){
ll ans2 = ans;
if (j + 'a' == s[i]) continue;
for (auto u:R_P[i]){
ll l = u.F - (i - u.S); // khat chap
if (l == 0) continue;
// cout << i << ' ' << u.F << ' ' << u.S << ' ' << l << '\n';
if (s[l - 1] == j + 'a'){
ans += BS(l - 1, i + 1);
ans ++;
}
}
for (auto u:L_P[i + 1]){
ll r = u.S + u.F - (i + 1);
if (r == n) continue;
if (j + 'a' == s[r]){
ans += BS(i, r + 1);
ans ++;
}
}
//res = max(res, ans);
//if (j == 2 && i == 1) cout << ans << '\n';
ans += p_l[i] + p_r[i];
res = max(res, ans);
//if (ans == 10) cout << i << ' ' << j << '\n';
ans = ans2;
}
}
cout << res;
return 0;
}
Compilation message
palinilap.cpp: In function 'int main()':
palinilap.cpp:115:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < s.size(); i++){
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5880 KB |
Output is correct |
| 2 |
Correct |
8 ms |
5880 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5880 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5880 KB |
Output is correct |
| 5 |
Correct |
8 ms |
5852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
6520 KB |
Output is correct |
| 2 |
Correct |
17 ms |
6520 KB |
Output is correct |
| 3 |
Correct |
21 ms |
6652 KB |
Output is correct |
| 4 |
Correct |
16 ms |
6392 KB |
Output is correct |
| 5 |
Correct |
19 ms |
6392 KB |
Output is correct |
| 6 |
Correct |
22 ms |
6520 KB |
Output is correct |
| 7 |
Correct |
21 ms |
6520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
408 ms |
20872 KB |
Output is correct |
| 2 |
Correct |
256 ms |
20196 KB |
Output is correct |
| 3 |
Correct |
238 ms |
20080 KB |
Output is correct |
| 4 |
Correct |
385 ms |
20872 KB |
Output is correct |
| 5 |
Correct |
384 ms |
20908 KB |
Output is correct |
| 6 |
Correct |
382 ms |
20856 KB |
Output is correct |
| 7 |
Correct |
386 ms |
20944 KB |
Output is correct |
| 8 |
Correct |
184 ms |
20112 KB |
Output is correct |
| 9 |
Correct |
391 ms |
20868 KB |
Output is correct |
| 10 |
Correct |
395 ms |
20872 KB |
Output is correct |
| 11 |
Correct |
239 ms |
20068 KB |
Output is correct |
| 12 |
Correct |
364 ms |
21684 KB |
Output is correct |
| 13 |
Correct |
376 ms |
20544 KB |
Output is correct |
| 14 |
Correct |
422 ms |
20728 KB |
Output is correct |
| 15 |
Correct |
387 ms |
20728 KB |
Output is correct |
| 16 |
Correct |
274 ms |
20160 KB |
Output is correct |
| 17 |
Correct |
377 ms |
20364 KB |
Output is correct |
| 18 |
Correct |
400 ms |
20344 KB |
Output is correct |
| 19 |
Correct |
377 ms |
20344 KB |
Output is correct |
