Pagini recente » Cod sursa (job #407076) | Cod sursa (job #1695697) | Cod sursa (job #661325) | Cod sursa (job #2244985) | Cod sursa (job #13337)
Cod sursa(job #13337)
#include <stdio.h>
#define NMAX 1000010
int n;
char s[NMAX];
char a[NMAX << 1];
int lung[NMAX << 1];
inline int MIN(int a, int b) { return (a < b) ? a : b; }
int main()
{
int i, q, lc, w;
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
scanf("%s", s);
for (i = 0; s[i]; i++) {
a[n++] = s[i];
a[n++] = '$';
}
int last = -1, j = -1;
long long rez = 0;
for (i = 0; i < n; i++) {
if (i > last) {
for (q = 1; i + q < n && i - q >= 0 && a[i - q] == a[i + q]; q++);
q--;
lung[i] = q;
last = i + q;
j = i;
} else {
w = 2 * j - i;
lc = MIN(lung[w], last - i);
if (lc == last - i) {
for (q = last - i + 1; i + q < n && i - q >= 0 && a[i - q] == a[i + q]; q++);
q--;
lc = q;
last = i + q;
j = i;
}
lung[i] = lc;
}
rez += (i & 1) ? (lung[i] + 1) / 2 : lung[i] / 2 + 1;
}
/* printf("%s\n", a);
for (i = 0; i < n; i++) printf("%d ", lung[i]);
printf("\n");
*/
printf("%lld\n", rez);
fclose(stdin);
fclose(stdout);
return 0;
}