Pagini recente » Cod sursa (job #1920613) | Cod sursa (job #2328601) | Cod sursa (job #1880121) | Cod sursa (job #1000281) | Cod sursa (job #981178)
Cod sursa(job #981178)
#include<cstdio>
#include<cstring>
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--)
if(i%2)
v[i]='#';
else
v[i]=v[i/2];
n=2*n+1;
for(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);
while(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)
if(i%2)
s+=d[i]/2;
else
s+=(d[i]+1)/2;
printf("%lld",s);
}