#include <stdio.h>
#include <string.h>
#define N 100100
#define A 26
long long max(long long a, long long b) { return a > b ? a : b; }
void manacher(char *cc, int *rr, int n) {
static char cc_[N * 2 + 1];
static int rr_[N * 2];
int i, o, x;
for (i = 0; i < n * 2 + 1; i++)
cc_[i] = i % 2 == 1 ? cc[i / 2] : ' ';
for (i = 0, o = 0, x = 0; i < n * 2 + 1; i++)
if (i + rr_[o + o - i] < x)
rr_[i] = rr_[o + o - i];
else {
o = i, x = max(x, i);
while (x >= 0 && x < n * 2 + 1 && cc_[x] == cc_[o + o - x])
x++;
rr_[i] = x - o;
}
for (i = 0; i <= n - 1 + n - 1; i++)
rr[i] = rr_[i + 1] / 2;
}
int main() {
static long long kk[N][A], ll[N], mm[N];
static int rr[N * 2];
static char cc[N + 1];
int n, h, i, i_, j, j_, ij, a;
long long k_;
scanf("%s", cc), n = strlen(cc);
manacher(cc, rr, n);
for (ij = 0; ij <= n - 1 + n - 1; ij++) {
h = ij / 2, i_ = h - rr[ij], j_ = ij - i_;
if (ij % 2 == 0) {
ll[h] += h - i_, ll[h + 1] -= (h - i_) * 2, ll[h + 2] += h - i_;
mm[h] -= h - i_, mm[h + 1] += (h - i_) * 2, mm[h + 2] -= h - i_;
}
ll[0] += h - i_, ll[1] -= h - i_;
ll[i_ + 1]--, ll[h + 1]++, ll[ij - h + 1]++, ll[j_ + 1]--;
mm[i_ + 1]++, mm[h + 1]--, mm[ij - h + 1]--, mm[j_ + 1]++;
if (i_ < 0 || j_ >= n)
continue;
i = i_, j = j_;
while (i >= 0 && j < n && (i == i_ || cc[i] == cc[j]))
i--, j++;
kk[i_][cc[j_] - 'a'] += i_ - i, kk[j_][cc[i_] - 'a'] += j_ - j;
}
for (i = 1; i < n; i++)
ll[i] += ll[i - 1];
for (i = 1; i < n; i++)
ll[i] += ll[i - 1];
for (i = 1; i < n; i++)
mm[i] += mm[i - 1];
for (i = 1; i < n; i++)
mm[i] += mm[i - 1];
k_ = 0;
for (i = 0; i < n; i++)
for (a = 0; a < A; a++)
k_ = max(k_, kk[i][a] + ll[i] + (cc[i] == a + 'a' ? mm[i] : 0));
printf("%lld\n", k_);
return 0;
}
Compilation message
palinilap.c: In function 'main':
palinilap.c:36:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | scanf("%s", cc), n = strlen(cc);
| ^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
1484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
24048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
