Pagini recente » Cod sursa (job #1703842) | Cod sursa (job #2761176) | Cod sursa (job #2700918) | Cod sursa (job #1992060) | Cod sursa (job #44725)
Cod sursa(job #44725)
#include <stdio.h>
#define NMAX 2000020
char S[NMAX], s[1000010];
long long V[NMAX];
int N;
int main()
{
int i, j, max, poz=0, num, d;
long long sum=0;
freopen("pscpld.in", "r", stdin);
gets(s);
N = strlen(s);
S[poz++] = ' ';
for (i = 0; i < N; i++)
S[poz++] = s[i], S[poz++] = ' ';
N = poz-1;
poz = 1; max = 1;
V[1] = 1; i = 1;
for (i = 2; i <= N; i++)
{
d = i-poz+1;
j = (d<=max)*(1+(V[poz-d+1]>>1));
num = (d<=max)*V[poz-d+1];
for (; (i>=j) && (i+j<= N) && (S[i-j]==S[i+j]); j++)
num += ((S[i-j]!=' ')<<1);
V[i] = num-(d>max)*(S[i]!=' ');
if ((max<V[i]) || (d==max)) max = V[i], poz = i;
}
for (i = 1; i <= N; i++) sum+=((V[i]>>1)+(V[i]&1));
freopen("pscpld.out", "w", stdout);
printf("%lld\n", sum);
return 0;
}