Pagini recente » Cod sursa (job #3154830) | Cod sursa (job #3274829) | Cod sursa (job #662618) | Cod sursa (job #1491320) | Cod sursa (job #942327)
Cod sursa(job #942327)
#include <stdio.h>
#include <string.h>
char in[1000100];
int x[2000100], sol[2000100];
int main() {
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
gets(in + 1);
int i, N = strlen(in + 1);
for (i = 1; i <= N; ++i)
x[2 * i] = in[i] - 'a' + 1;
N = 2 * N + 1; x[0] = -1; x[N + 1] = -2;
int center = -1000, right = -1000;
for (i = 1; i <= N; ++i) {
int st, dr;
st = dr = i;
if (i > right)
///sol[i] = (i % 2 == 0) ? 1 : 0;
sol[i]=0;
else {
int radius = i - center;
sol[i] = sol[center - radius];
if (i + sol[i] > right)
sol[i] = right - i;
st = st - sol[i]; dr = dr + sol[i];
}
while (x[st-1] == x[dr+1]) {
--st; ++dr;
///if (x[st] > 0 && x[st] == x[dr])
++sol[i];
}
if (dr > right)
right = dr, center = i;
}
long long stot = 0;
for (i = 1; i <= N; ++i)
stot += (sol[i]+1)/2;
printf("%lld", stot);
return 0;
}