#include <stdio.h>
#include <string.h>
#define N 100000
#define N_ (N * 2 + 1)
#define A 26
int min(int a, int b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
char cc_[N_ + 1]; int aa0[N_], aa1[N_], sa[N_], pp[N_], st[N_ * 2], n_;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (aa0[ii[j]] == aa0[i_])
j++;
else if (aa0[ii[j]] < aa0[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
void compress() {
int i, a;
for (i = 0, a = 0; i < n_; i++)
aa0[sa[i]] = i + 1 == n_ || aa0[sa[i + 1]] != aa0[sa[i]] || aa1[sa[i + 1]] != aa1[sa[i]] ? a++ : a;
}
void extend(int m) {
int i;
for (i = 0; i < n_; i++)
aa1[i] = i + m < n_ ? aa0[i + m] : -1;
}
void sort_(int *aa, int *ii, int *jj) {
static int kk[N_ + 2];
int i, j, a;
memset(kk, 0, (n_ + 2) * sizeof *kk);
for (i = 0; i < n_; i++) {
a = aa[i] + 1;
kk[a + 1]++;
}
for (a = 1; a <= n_ + 1; a++)
kk[a] += kk[a - 1];
for (i = 0; i < n_; i++) {
j = ii[i], a = aa[j] + 1;
jj[kk[a]++] = j;
}
}
void build() {
int m, i, j, a, p;
for (i = 0; i < n_; i++) {
sa[i] = i;
aa0[i] = cc_[i];
}
sort(sa, 0, n_);
compress();
for (m = 1; m < n_; m <<= 1) {
extend(m);
sort_(aa1, sa, pp);
sort_(aa0, pp, sa);
compress();
}
for (i = 0, p = 0; i < n_; i++, p--) {
a = aa0[i];
if (a + 1 < n_) {
j = sa[a + 1], p = max(p, 0);
while (i + p < n_ && cc_[i + p] == cc_[j + p])
p++;
pp[a] = p;
}
}
for (a = 0; a < n_; a++)
st[n_ + a] = pp[a];
for (i = n_ - 1; i > 0; i--)
st[i] = min(st[i << 1 | 0], st[i << 1 | 1]);
}
int lcp(int i, int j) {
int l, r, tmp, p;
if (i < 0 || i >= n_ || j < 0 || j >= n_)
return 0;
l = aa0[i], r = aa0[j];
if (l > r)
tmp = l, l = r, r = tmp;
if (l == r)
return n_ - sa[l];
r--;
p = n_;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
p = min(p, st[l++]);
if ((r & 1) == 0)
p = min(p, st[r--]);
}
return p;
}
int main() {
static long long kk[N][A], ll[N + 2], mm[N + 2];
static char cc[N + 1];
int n, h, i, i_, j_, ij, a;
long long k_;
scanf("%s", cc), n = strlen(cc), n_ = n * 2 + 1;
for (i = 0; i < n; i++)
cc_[i] = cc_[n + n - i] = cc[i];
cc_[n] = ' ';
build();
for (ij = 0; ij <= n - 1 + n - 1; ij++) {
int p;
h = ij / 2, p = lcp(n + n - h, ij - h), i_ = h - p, 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;
p = lcp(n + n - i_ + 1, j_ + 1) + 1;
kk[i_][cc[j_] - 'a'] += p, kk[j_][cc[i_] - 'a'] += p;
}
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:126:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
126 | scanf("%s", cc), n = strlen(cc), n_ = n * 2 + 1;
| ^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
332 KB |
Output is correct |
| 5 |
Correct |
0 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1612 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1644 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1680 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1100 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1484 KB |
Output is correct |
| 6 |
Correct |
8 ms |
1704 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
256 ms |
27948 KB |
Output is correct |
| 2 |
Correct |
154 ms |
27944 KB |
Output is correct |
| 3 |
Correct |
146 ms |
27896 KB |
Output is correct |
| 4 |
Correct |
251 ms |
27824 KB |
Output is correct |
| 5 |
Correct |
264 ms |
27900 KB |
Output is correct |
| 6 |
Correct |
247 ms |
27848 KB |
Output is correct |
| 7 |
Correct |
249 ms |
27844 KB |
Output is correct |
| 8 |
Correct |
132 ms |
7620 KB |
Output is correct |
| 9 |
Correct |
259 ms |
27896 KB |
Output is correct |
| 10 |
Correct |
271 ms |
27908 KB |
Output is correct |
| 11 |
Correct |
157 ms |
27832 KB |
Output is correct |
| 12 |
Correct |
175 ms |
27908 KB |
Output is correct |
| 13 |
Correct |
164 ms |
27896 KB |
Output is correct |
| 14 |
Correct |
229 ms |
27908 KB |
Output is correct |
| 15 |
Correct |
235 ms |
27924 KB |
Output is correct |
| 16 |
Correct |
149 ms |
27844 KB |
Output is correct |
| 17 |
Correct |
330 ms |
27996 KB |
Output is correct |
| 18 |
Correct |
248 ms |
28008 KB |
Output is correct |
| 19 |
Correct |
290 ms |
27992 KB |
Output is correct |
