Pagini recente » Cod sursa (job #2810793) | Cod sursa (job #2035610) | Cod sursa (job #1823358) | Cod sursa (job #2847494) | Cod sursa (job #942312)
Cod sursa(job #942312)
#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] = x[N + 1] = -1;
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;
else {
int radious = right - center;
sol[i] = sol[center - radious];
if (sol[i] > radious)
sol[i] = radious;
st = st - sol[i]; dr = dr + sol[i];
}
while (x[st] == x[dr]) {
--st; ++dr;
if (x[st] > 0 && x[st] == x[dr])
++sol[i];
}
if (dr > right)
right = dr - 1, center = i;
}
long long stot = 0;
for (i = 1; i <= N; ++i)
stot += sol[i];
printf("%lld", stot);
return 0;
}