Pagini recente » Cod sursa (job #475374) | Cod sursa (job #1923134) | Monitorul de evaluare | Cod sursa (job #97815) | Cod sursa (job #2774897)
#include<stdio.h>
#include<string.h>
int n,d[2000010],i,b;
char v[2000010];
long long s;
int main()
{
freopen("pscpld.in","r",stdin),freopen("pscpld.out","w",stdout),scanf("%s",v+1),n=strlen(v+1);
for(i=2*n+1;i;--i)
v[i]=i%2?'#':v[i/2];
for(n=2*n+1,i=1;i<=n;++i) {
if(b+d[b]>=i)
d[i]=(b+d[b]-i>d[2*b-i])?d[2*b-i]:(b+d[b]-i);
for(;i-d[i]>1&&i+d[i]+1<=n&&v[i-d[i]-1]==v[i+d[i]+1];++d[i]);
if(i+d[i]>=b+d[b])
b=i;
}
for(i=1;i<=n;++i)
s+=(i%2?(d[i]/2):(d[i]+1)/2);
printf("%lld",s);
return 0;
}