#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair <int , int>
#define F first
#define S second
const int N = 1e5 + 10, B = 101, MOD = 1e9 + 7, X = 11;
int Hash[N], revHash[N], P[N], s[N], q[N], Q1[N], Q2[N], ps1[N], ps2[N], n, cnt = 0;
vector <int> V[N][26];
//functions
int mod(int a) {return (a % MOD + MOD) % MOD;}
int HASH(int l, int r)
{
if (l == 0) return Hash[r];
return mod(Hash[r] - Hash[l - 1] * P[r - l + 1]);
}
int REVHASH(int l, int r)
{
return mod(revHash[l] - revHash[r + 1] * P[r - l + 1]);
}
int val(int l1, int r1, int l2, int r2)
{
if (l1 < 0 || l2 < 0 || r1 >= n || r2 >= n) return 0;
return (REVHASH(l1, r1) == HASH(l2, r2));
}
int BS(int l1, int l2)
{
if (l1 < 0 || l2 < 0 || l1 >= n || l2 >= n) return -1;
if (s[l1] != s[l2]) return -1;
int L = 0, R = min(l1, n - l2 - 1) + 1;
while (R - L > 1) {
int md = (R + L) / 2;
if (val(l1 - md, l1, l2, l2 + md)) L = md;
else R = md;
}
return L;
}
//end
int32_t main()
{
//preprocess
P[0] = 1;
for (int i = 1; i < N; i ++) P[i] = (P[i - 1] * B) % MOD;
//Input
string st; cin >> st;
n = st.size();
for (int i = 0; i < n; i ++) s[i] = st[i] - 'a';
//set Hash
Hash[0] = s[0] + X;
for (int i = 1; i < n; i ++) {
Hash[i] = (Hash[i - 1] * B + s[i] + X) % MOD;
}
revHash[n - 1] = s[n - 1] + X;
for (int i = n - 2; i >= 0; i --) {
revHash[i] = (revHash[i + 1] * B + s[i] + X) % MOD;
}
//end
for (int i = 0; i < n; i ++) {
int t = BS(i, i);
if (i - t - 1 >= 0) V[i - t - 1][s[i + t + 1]].push_back(i + t + 1);
if (i + t + 1 < n) V[i + t + 1][s[i - t - 1]].push_back(i - t - 1);
if (t != 0) {
ps1[i]--;
ps1[i + t]++;
Q1[i] = -t;
}
if (t != 0) {
ps2[i]--;
ps2[i - t]++;
Q2[i] = -t;
}
cnt += t + 1;
}
for (int i = 0; i < n - 1; i ++) {
int t = BS(i, i + 1);
if (i - t - 1 >= 0) V[i - t - 1][s[i + t + 2]].push_back(i + t + 2);
if (i + t + 2 < n) V[i + t + 2][s[i - t - 1]].push_back(i - t - 1);
if (t == -1) continue;
ps1[i]--;
ps1[i + t + 1]++;
Q1[i] = -(t + 1);
ps2[i + 1]--;
ps2[i - t]++;
Q2[i + 1] = -(t + 1);
cnt += t + 1;
}
for (int i = n - 2; i >= 0; i --) ps1[i] += ps1[i + 1];
for (int i = 1; i < n; i ++) ps2[i] += ps2[i - 1];
Q1[n - 1] += ps1[n - 1];
for (int i = n - 2; i >= 0; i --) Q1[i] += ps1[i] + Q1[i + 1];
Q2[0] += ps2[0];
for (int i = 1; i < n; i ++) Q2[i] += ps2[i] + Q2[i - 1];
for (int i = 0; i < n; i ++) q[i] = Q1[i] + Q2[i];
//find ans
int ans = cnt;
for (int i = 0; i < n; i ++) for (int c = 0; c < 26; c ++){
int val = 0;
for (auto j : V[i][c]) {
if (j < 0 || j >= n) continue ;
if (i < j) val += BS(i - 1, j + 1) + 2;
else val += BS(j - 1, i + 1) + 2;
}
//cout << i << " " << c << " " << val << "\n";
ans = max(ans, cnt + val - q[i]);
}
//Output
cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
62204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
62840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
262 ms |
74604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
